연습문제
레이저 게임
- 난이도
- Lv. 5
- 제출
- 63 명
- 참가자
- 26 명
- 정답률
- 60.00 %
- 지원 언어
-
CC++JavaPythonRust
로그인 후 문제풀이가 가능합니다.
언어별 시간/메모리
언어 | 시간 | 메모리 |
---|---|---|
Python | 5초 | 1024MB |
Java | 3초 | 1024MB |
C++ | 1초 | 1024MB |
C | 1초 | 1024MB |
Rust | 1초 | 1024MB |
코드런 나라에서 레이저 게임이 열립니다. 이 게임은 2차원 격자 형태의 보드판에서 세 명의 플레이어가 한 팀이 되어 진행합니다. 보드판의 각 칸에는 정수가 적혀 있으며, 세 명의 플레이어는 협력하여 최고 점수를 얻어야 합니다. 플레이어들은 순서로 아래와 같은 규칙에 따라 행동합니다.
플레이어 : 가로 또는 세로 방향 중 하나를 선택해 원하는 범위에 레이저를 발사합니다. 가 발사한 레이저가 지나간 모든 칸의 값은 로 변합니다.
플레이어 : 가 선택한 방향과 다른 방향에서(가 가로를 선택했다면 세로, 세로를 선택했다면 가로) 원하는 범위에 레이저를 발사합니다. 가 발사한 레이저가 지나간 칸의 값은 배가 됩니다.
플레이어 : 와 의 행동으로 변경된 보드판을 기준으로 특정 직사각형을 선택합니다. 이 직사각형 안의 모든 숫자의 합이 세 명의 플레이어가 협력해서 얻은 최종 점수가 됩니다.
단, 와 는 각각 한 개 이상의 행 또는 열에 레이저를 발사해야 하며 는 한 개 이상의 격자 칸으로 이루어진 직사각형을 선택해야 합니다.
아래는 격자에서 가 가로 방향을 선택해 [2 ~ 3] 행에 레이저를 발사하고 가 세로 방향으로 [3 ~ 4]열에 레이저를 발사한 후 가 행 열에서 행 열까지 격자에 해당하는 직사각형을 선택한 예시입니다. 이 경우 최종 점수는 입니다.
보드판이 주어졌을 때 세 명의 플레이어가 협력하여 얻을 수 있는 최대 점수를 출력하세요.
제약조건
[문제 제약 조건]
[조건 1]
[조건 2] 보드판에 적혀 있는 정수
[서브 태스크별 제약 조건]
Subtask1 (31점):
Subtask2 (20점):
Subtask3 (49점): 문제 조건 외에 별도의 제한이 없습니다.
입력형식
첫째 줄에 보드판의 길이를 나타내는 정수 N
이 주어집니다.
다음 N
개의 줄에 걸쳐 보드판에 적혀 있는 정수값 N
개가 공백을 사이에 두고 주어집니다.
출력형식
세 명의 플레이어가 협업을 해서 얻을 수 있는 최대 점수를 출력합니다.
입력예제1
3 -1 -1 -1 4 -1 1 1 -1 4
출력예제1
24
플레이어 가 세로를 선택해서 [2 ~ 2]열에 레이저를 발사하고, 플레이어 는 가로를 선택해서 [2 ~ 3]행에 레이저를 발사하고, 플레이어 는 2 ~ 3행 전체에 해당하는 직사각형을 선택하면 최댓값인 를 얻을 수 있습니다.
입력예제2
3 -2 -3 -2 -1 -2 -1 0 2 2
출력예제2
20
플레이어 가 가로를 선택해서 [1 ~ 2]행에 레이저를 발사하고, 플레이어 는 세로를 선택해서 [1 ~ 3]열에 레이저를 발사하고, 플레이어 는 전체 직사각형을 선택하면 최댓값인 을 얻을 수 있습니다.
입력예제3
2 3 3 3 3
출력예제3
16
플레이어 가 레이저를 발사하면 점수에 손해를 보지만, 반드시 레이저를 발사해야 합니다. 따라서 가 가로를 선택해서 [1 ~ 1]행에 레이저를 발사하고, 플레이어 는 세로를 선택해서 [1 ~ 2]열에 레이저를 발사하고, 플레이어 는 전체 직사각형을 선택하면 최댓값인 을 얻을 수 있습니다.