문제
N×M 격자에서 (1,1)에서 (N,M)까지 왼쪽, 오른쪽, 아래로만 이동할 수 있다 (위로는 불가). 각 칸의 값을 수집할 때 최대 합을 구하라.
입력
첫째 줄에 N, M (1 이상 1,000 이하), 이후 N×M 격자 값이 주어진다.
출력
수집한 값의 최대 합을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 5 10 25 7 8 13 68 24 -78 63 32 12 -69 100 -29 -25 -16 -22 -57 -33 99 7 -76 -11 77 15 | 319 |
풀이
행 단위 DP로, 각 행에서 왼쪽→오른쪽과 오른쪽→왼쪽 두 방향을 모두 고려한다.
- 첫 행은 왼쪽에서 오른쪽으로 누적합을 계산한다
- 이후 각 행에서 왼쪽→오른쪽 방향 최대값(
tmp[0])을 구한다:max(위에서 내려온 값, 왼쪽에서 온 값) + 현재 칸 - 오른쪽→왼쪽 방향 최대값(
tmp[1])도 동일하게 구한다 dp[i][j] = max(tmp[0][j], tmp[1][j])로 두 방향 중 큰 값을 선택한다
핵심 아이디어: 위로 이동 불가이므로 행 단위로 처리할 수 있다. 같은 행 내에서 좌→우, 우→좌 두 번의 스캔으로 수평 이동을 모두 고려한다.
코드
package day399;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Day378BOJ2169로봇조종하기 {
static int N, M;
static int[][] map, dp, tmp;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
map = new int[N][M];
dp = new int[N][M];
tmp = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++)
map[i][j] = Integer.parseInt(st.nextToken());
}
dp[0][0] = map[0][0];
for (int i = 1; i < M; i++)
dp[0][i] = dp[0][i - 1] + map[0][i];
for (int i = 1; i < N; i++) {
tmp[0][0] = dp[i - 1][0] + map[i][0];
for (int j = 1; j < M; j++)
tmp[0][j] = Math.max(tmp[0][j - 1], dp[i - 1][j]) + map[i][j];
tmp[1][M - 1] = dp[i - 1][M - 1] + map[i][M - 1];
for (int j = M - 2; j >= 0; j--)
tmp[1][j] = Math.max(tmp[1][j + 1], dp[i - 1][j]) + map[i][j];
for (int j = 0; j < M; j++)
dp[i][j] = Math.max(tmp[0][j], tmp[1][j]);
}
System.out.println(dp[N - 1][M - 1]);
br.close();
}
}복잡도
- 시간: O(N * M)
- 공간: O(N * M)