문제 이해
내려가기 게임을 하려 한다.
현재 위치에서 다음 줄로 내려갈 때 바로 아래, 혹은 바로 아래의 수의 양 옆 위치만 갈 수 있다.(즉, 아래와 대각선)
맨 위에서부터 맨 아래까지 이동하려고 한다.
모든 칸마다 점수가 존재할 때, 내려가기 게임을 하면서 밟는 점수의 총합의 최솟값, 최댓값을 구하는 문제이다.
문제 풀이
사실 문제 자체는 간단하다고 생각한다.
항상 "현재의 상황"에서 과거를 생각하며 풀어야 한다.
현재 arr[N][0]의 위치에 존재할 경우 과거에는 arr[N-1][0] 혹은 arr[N-1][1]에 존재했을 것이다.
arr[N][1]이라면 과거에는 arr[N-1][0], arr[N-1][1], arr[N-1][2] 중 한 곳에, arr[N][2]라면 arr[N-1][1], arr[N-1][2] 중 한 곳에 존재했을 것이다.
문제는 메모리 제한이 존재한다는 점이다.
만약 DP를 위한 배열을 N *3만큼 준비한다면 메모리 초과가 발생함을 알 수 있다. 왜냐하면 우리는 최댓값, 최솟값을 모두 구해야 하기 때문에 cost를 저장한 배열을 재활용할 수 없으며, 최댓값과 최솟값의 중간 계산 값을 저장할 max, min 배열을 추가로 준비해 줘야하기 때문이다.
즉, N*3 배열이 3개 필요하므로 메모리 초과가 발생한다.
우리는 이 조건을 알고 있어야 한다.
"2번째 전 상황은 현재 상황에 직접적으로 영향을 끼치진 못한다"
우리는 무조건 아래로 한 칸 밖에 이동할 수 없으므로, 2번째 전 상황은 이전 상황에 모두 반영될 것이다. 또, 더 이상 2번째 전 상황을 사용할 일은 없다. 마찬가지로 3번째 전 상황도 2번째 전 상황에 모두 반영되어 있을 것이다.
즉, Max와 Min을 위한 배열은 N*3만큼 필요하지 않고, 오로지 "현재 상황에서의 최대, 최솟값", "바로 이전 상황에서의 최대, 최솟값"을 위한 2개 공간만 필요하고, 2*3 배열로도 충분히 이 문제를 해결할 수 있다는 것이다.
코드
import java.io.*;
import java.util.*;
public class Main {
static StringBuilder sb = new StringBuilder();
static int N, S, M;
static int[][] list;
static int[][] max;
static int[][] min;
static int answer = -1;
static void dp() {
for(int i =0;i<3;i++) {
max[0][i] = list[0][i];
min[0][i] = list[0][i];
}
for(int i =1;i<N;i++) {
int prev = (i+1)%2;
/*
max, min은 2*3 행렬이므로, 직전 max, min 값은
now-1 위치가 될 것이다
그런데, now는 0 혹은 1이므로, now-1로 설정하면 음수가 나올 수 있다
따라서, 2로 나눈 나머지는 어차피 0 혹은 1만 나오므로 오히려
now + 1을 수행한 뒤 2로 나눈 나머지를 prev로 설정하면
무조건 now와는 다른 값이 나올 것이다.
*/
int now = i%2;
// 현재 max, min 값을 now 행에 저장할 것이다.
for(int j =0;j<3;j++) {
max[now][j] = Integer.MIN_VALUE;
min[now][j] = Integer.MAX_VALUE;
for(int s:new int[] {j-1,j,j+1}) {
/*
현재 내가 존재하는 위치는 arr[now][j]이다.
직전에 나는 arr[now-1][j], arr[now-1][j-1],
arr[now-1][j+1] 중 한 곳에 위치해 있었을 것이다.
따라서, s가 j-1, j ,j+1인 상황 모두를 고려하되,
s가 배열 범위를 넘어가는 경우는 계산을 수행하지 않으면 될 것이다.
*/
if(s<0||s>2) continue;
max[now][j] = Math.max(max[now][j], list[i][j]
+ max[prev][s]);
min[now][j] = Math.min(min[now][j], list[i][j]
+ min[prev][s]);
// max[now][j] : 원래 저장되어 있는 값
// vs 이전에 가능한 위치 중 max값 + 현재 cost
// min[now][j] : 원래 저장되어 있는 값
// vs 이전에 가능한 위치 중 min값 + 현재 cost
}
}
}
}
public static void main(String[] args) throws IOException {
FastReader sc = new FastReader();
N = sc.nextInt();
list = new int[N][3];
max = new int[2][3];
min = new int[2][3];
for(int i =0;i<N;i++) {
for(int j =0;j<3;j++) {
list[i][j] = sc.nextInt();
}
}
dp();
int index = (N+1)%2;
// max, min 중 마지막에 Update된 위치는 (N-1)%2 행이 될 것이다.
// 위에서 말했듯, 2로 나눈 나머지는 0 혹은 1이므로
// (N+1)%2 = (N-1)%2이 될 것이다.
int ans_max = Integer.MIN_VALUE;
int ans_min = Integer.MAX_VALUE;
for(int i =0;i<3;i++) {
ans_max = Math.max(max[index][i],ans_max);
ans_min = Math.min(min[index][i],ans_min);
}
System.out.println(ans_max+" "+ans_min);
}
static class FastReader // 빠른 입력을 위한 클래스
}
결과
-
8,9번째 줄 메모리 초과 : max, min도 N*3 공간만큼 준비하여 중간값을 저장했는데, 이럴 경우 메모리 초과 문제가 발생했다.
-
6,7번째 줄 런타임 에러 : max와 min을 2*4 행렬로 만들어 0,1,2가 아닌 1,2,3으로 코드를 구현해보려고 했는데, 이 과정에 실수가 생겨 틀렸다.
-
3,4,5번째 줄 틀렸습니다 : max와 min을 2*4 행렬로 만들어 0,1,2가 아닌 1,2,3으로 코드를 구현해보려고 했는데, 원래 나의 코드 습관이 0 index부터 시작하는 코드를 좋아해서 많은 실수가 있었다. 그래서 덜 직관적일 수는 있지만 나에게 편한 0,1,2 index 사용을 통해 문제를 해결했다.
