백준 2169번 https://www.acmicpc.net/problem/2169
문제
NASA에서는 화성 탐사를 위해 화성에 무선 조종 로봇을 보냈다. 실제 화성의 모습은 굉장히 복잡하지만, 로봇의 메모리가 얼마 안 되기 때문에 지형을 N×M 배열로 단순화 하여 생각하기로 한다.
지형의 고저차의 특성상, 로봇은 움직일 때 배열에서 왼쪽, 오른쪽, 아래쪽으로 이동할 수 있지만, 위쪽으로는 이동할 수 없다. 또한 한 번 탐사한 지역(배열에서 하나의 칸)은 탐사하지 않기로 한다.
각각의 지역은 탐사 가치가 있는데, 로봇을 배열의 왼쪽 위 (1, 1)에서 출발시켜 오른쪽 아래 (N, M)으로 보내려고 한다. 이때, 위의 조건을 만족하면서, 탐사한 지역들의 가치의 합이 최대가 되도록 하는 프로그램을 작성하시오.
입력
첫째 줄에 N, M(1≤N, M≤1,000)이 주어진다. 다음 N개의 줄에는 M개의 수로 배열이 주어진다. 배열의 각 수는 절댓값이 100을 넘지 않는 정수이다. 이 값은 그 지역의 가치를 나타낸다.
출력
첫째 줄에 최대 가치의 합을 출력한다.
예제
입력
1
2
3
4
5
6
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
출력
1
319
이 문제에서 집중해야할 점은 다음과 같다.
- 로봇이 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있다.
- 위로 이동하지 못한다.
- 오른쪽 아래로 이동해야한다.
- 무조건 맨 아래로 이동해야한다.
맨 아랫줄로 이동해야 하지만 아래서 위로 이동하지 못하기 때문에 아래로 내려오기 전에 현재 줄에 존재하는 칸의 최댓값을 구하는 방법을 찾으면 된다. 즉, 한 줄에 존재하는 각 칸의 최댓값을 구하고, 아래로 내려가면 점진적으로 해결할 수 있다.
일단 출발지가 (1, 1)이기 때문에 맨 윗줄에서는 오른쪽으로 이동하는 것만 가능하다.
1
2
3
for (int i = 1; i < m; i++) {
sum[0][i] = sum[0][i-1] + value[0][i];
}
두번째 줄부터는 도착하기 위해서 아래로 이동해야하기 때문에 윗칸에서 일자로 내려왔을 때의 값을 구해준다. 이 값을 기준으로 오른쪽으로 이동했을 때와 왼쪽으로 이동했을 때의 각 값을 구한다.
1
2
3
4
5
6
7
8
9
10
11
for (int i = 1; i < n; i++) {
for (int j = 0; j < m; j++) { // 위에서 아래로
nums[j][0] = sum[i-1][j] + value[i][j];
}
for (int j = 1; j < m; j++) { // 왼쪽에서 오른쪽
nums[j][1] = Math.max(nums[j-1][1] + value[i][j], nums[j][0]);
}
for (int j = m-2; j >= 0; j--) { // 오른쪽에서 왼쪽
nums[j][2] = Math.max(nums[j+1][2] + value[i][j], nums[j][0]);
}
}
위의 세 개의 값 중 최댓값이 현재 칸까지의 최대 가치가 된다.
주의해야할 점은 왼쪽에서 오른쪽으로 이동하거나 오른쪽에서 왼쪽으로 이동할 때이다. 로봇이 이동하기 전에 윗줄에서 올 수도 있고, 같은 줄(왼쪽이나 오른쪽)에서 올수도 있다. 두 개의 값을 비교하여 큰 값을 사용한다.
코드 (Java)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Bj2169 {
private static int n, m;
private static int[][] value;
private static int[][] sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer sb = new StringTokenizer(br.readLine());
n = Integer.parseInt(sb.nextToken());
m = Integer.parseInt(sb.nextToken());
value = new int[n][m];
sum = new int[n][m];
for (int i = 0; i < n; i++) {
sb = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
value[i][j] = Integer.parseInt(sb.nextToken());
}
}
sum[0][0] = value[0][0];
int[][] nums = new int[m][3];
for (int i = 1; i < m; i++) { // 첫번째줄
sum[0][i] = sum[0][i-1] + value[0][i];
}
for (int i = 1; i < n; i++) { // 두번째줄부터
for (int j = 0; j < m; j++) { // 위에서 아래로
nums[j][0] = sum[i-1][j] + value[i][j];
}
nums[0][1] = nums[0][0];
for (int j = 1; j < m; j++) { // 왼쪽에서 오른쪽
nums[j][1] = Math.max(nums[j-1][1] + value[i][j], nums[j][0]);
}
nums[m-1][2] = nums[m-1][0];
for (int j = m-2; j >= 0; j--) { // 오른쪽에서 왼쪽
nums[j][2] = Math.max(nums[j+1][2] + value[i][j], nums[j][0]);
}
for (int j = 0; j < m; j++) {
sum[i][j] = Math.max(nums[j][1], nums[j][2]);
}
}
System.out.println(sum[n-1][m-1]);
}
}