문제
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 NxM 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M(1<=N, M<=1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.
출력
첫째 줄에 최대 가치의 합을 출력한다.
풀이
위로는 갈 수 없지만 한 행 안에서는 좌우 이동이 모두 가능해서, 단순한 dp[i][j] = max(위, 왼쪽) 형태로는 해결되지 않는다. 같은 행 안에서 왼쪽으로 갔다가 다시 오른쪽으로 오거나, 반대로 움직일 수 있기 때문이다.
코드에서는 한 행을 처리할 때 두 방향을 따로 계산한다. tempSum[0][j]는 왼쪽에서 오른쪽으로 훑으면서 구한 최댓값이고, tempSum[1][j]는 오른쪽에서 왼쪽으로 훑으면서 구한 최댓값이다.
각 방향에서 현재 칸에 올 수 있는 방법은 두 가지다. 위에서 내려오거나, 같은 행에서 직전 칸에서 오는 것이다. 두 경우 중 큰 값을 택해 누적하면 된다. 그리고 마지막에 두 방향 결과 중 더 큰 값을 dp[i][j]로 저장한다.
이렇게 하면 "한 행 안에서는 한 방향으로만 진행한다"는 조건을 자연스럽게 강제할 수 있어서, 같은 칸을 다시 방문하는 잘못된 경로가 섞이지 않는다.
코드
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static int[][] field, dp;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
field = new int[N][M];
dp = new int[N][M];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++)
field[i][j] = Integer.parseInt(st.nextToken());
}
solve();
System.out.println(dp[N - 1][M - 1]);
}
static void solve() {
// 첫 줄 해결
dp[0][0] = field[0][0];
for (int j = 1; j < M; j++)
dp[0][j] = dp[0][j - 1] + field[0][j];
int[][] tempSum = new int[2][M];
for (int i = 1; i < N; i++) {
tempSum[0][0] = dp[i - 1][0] + field[i][0];
for (int j = 1; j < M; j++)
tempSum[0][j] = Math.max(dp[i - 1][j], tempSum[0][j - 1]) + field[i][j];
tempSum[1][M - 1] = dp[i - 1][M - 1] + field[i][M - 1];
for (int j = M - 2; j >= 0; j--)
tempSum[1][j] = Math.max(dp[i - 1][j], tempSum[1][j + 1]) + field[i][j];
for (int j = 0; j < M; j++)
dp[i][j] = Math.max(tempSum[0][j], tempSum[1][j]);
}
}
}복잡도
- 시간 복잡도:
- 공간 복잡도:
마무리
처음에 문제를 봤을 때는 막막했지만, 한 행을 왼쪽에서 한 번 보고 오른쪽에서 한 번 보는 아이디어만 떠올리면 정리가 된다. 위로 못 올라간다는 조건 때문에 오히려 행 단위 DP가 잘 맞는 문제다.
