첫번째 시도
생각끝에 일단 막무가내로, dp[n] = dp[n-1] + (N-1과 다른 색 중 최솟값) 으로 풀어보았다.import java.io.*; import java.util.*; public class Main{ static int red = -1; static int green = -2; static int blue = -3; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n]; StringTokenizer st; st = new StringTokenizer(br.readLine()); //점화식 //dp[n] = dp[n-1] + (N-1과 다른 색 중 최솟값) //초기값 설정 int r = Integer.parseInt(st.nextToken()); int g = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); int min = -1; int color = 0; if(r < g){ min = r; color = red; } if(r > g){ min = g; color = green; } //여기서 min은 r or g if(min > b){ min = b; color = blue; } dp[0] = min; //테이블 채우기 for(int i = 1; i < n; i++){ st = new StringTokenizer(br.readLine()); r = Integer.parseInt(st.nextToken()); g = Integer.parseInt(st.nextToken()); b = Integer.parseInt(st.nextToken()); min = -1; if(color == red){ r = 1001; }else if(color == green){ g = 1001; } else if (color == blue) { b = 1001; } if(r < g && color != red){ min = r; color = red; } if(r > g && color != green){ min = g; color = green; } //여기서 min은 r or g if(min > b && color != blue){ min = b; color = blue; } dp[i] = min + dp[i-1]; } System.out.println(dp[n-1]); } }우선 답은 틀렸지만, IDE로 돌려본 결과 5개의 테스트 케이스 중 앞에 4개는 정답이었다.
오답인 이유에 대해서 생각해본 바로는, 문제를 풀면서도 생각했었지만
테이블을 채우다가 지금 현재 주어진 rgb로 인해 과거가 바뀔 가능성이 있는게 아닌가 라고 생각했다.
예를 들면,
첫번째 1 2 3 : min=1, dp[1]=1
두번째 3 2 1 : min=1, dp[2]=2 까지 했는데
세번째로 100 100 1 이 주어진다면, 100 밖에 선택지가 없어서 dp[3]=102가 된다. 따라서 세번째에서 1을 고르기 위해선 과거의 테이블을 바꾸어야 한다.
이를 해결하기 위해 다음과 같이 시도해보았다.
두번째 시도
초기값을 r, g, b 각 3가지 경우로 모두 실행해보고, 그 3가지 결과 중에서 최솟값을 고르는 것이다. 따라서 초기값을 각 3가지로 두는 경우에 대해 3개의 테이블을 채워보아야 한다. 코드는 그냥 무식하게 말 그대로 작성해보았다.import java.io.*; import java.util.*; public class Main static int red = -1; static int green = -2; static int blue = -3; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] dp = new int[n]; int[] dp2 = new int[n]; int[] dp3 = new int[n]; int[] arrR = new int[n]; int[] arrG = new int[n]; int[] arrB = new int[n]; StringTokenizer st; st = new StringTokenizer(br.readLine()); arrR[0] = Integer.parseInt(st.nextToken()); arrG[0] = Integer.parseInt(st.nextToken()); arrB[0] = Integer.parseInt(st.nextToken()); int color = 0; int color2 = 0; int color3 = 0; //각 3가지 경우에 대한 초기값 설정 dp[0] = arrR[0]; color = red; dp2[0] = arrG[0]; color2 = green; dp3[0] = arrB[0]; color3 = blue; int min; int r, g, b; for (int i = 1; i < n; i++){ st = new StringTokenizer(br.readLine()); arrR[i] = Integer.parseInt(st.nextToken()); arrG[i] = Integer.parseInt(st.nextToken()); arrB[i] = Integer.parseInt(st.nextToken()); } //첫번째로 R을 선택한 경우의 테이블 채우기 for(int i = 1; i < n; i++){ r = arrR[i]; g = arrG[i]; b = arrB[i]; min = -1; if(color == red){ r = 1001; }else if(color == green){ g = 1001; } else if (color == blue) { b = 1001; } if(r < g && color != red){ min = r; color = red; } if(r > g && color != green){ min = g; color = green; } //여기서 min은 r or g if(min > b && color != blue){ min = b; color = blue; } dp[i] = min + dp[i-1]; } //첫번째로 G를 선택한 경우의 테이블 채우기 for(int i = 1; i < n; i++){ r = arrR[i]; g = arrG[i]; b = arrB[i]; min = -1; if(color2 == red){ r = 1001; }else if(color2 == green){ g = 1001; } else if (color2 == blue) { b = 1001; } if(r < g && color2 != red){ min = r; color2 = red; } if(r > g && color2 != green){ min = g; color2 = green; } //여기서 min은 r or g if(min > b && color2 != blue){ min = b; color2 = blue; } dp2[i] = min + dp2[i-1]; } //첫번째로 B를 선택한 경우의 테이블 채우기 for(int i = 1; i < n; i++){ r = arrR[i]; g = arrG[i]; b = arrB[i]; min = -1; if(color3 == red){ r = 1001; }else if(color3 == green){ g = 1001; } else if (color3 == blue) { b = 1001; } if(r < g && color3 != red){ min = r; color3 = red; } if(r > g && color3 != green){ min = g; color3 = green; } //여기서 min은 r or g if(min > b && color3 != blue){ min = b; color3 = blue; } dp3[i] = min + dp3[i-1]; } //각 경우에 대한 3개의 테이블 중 최솟값이 나온 결과 출력 int answer = Math.min(Math.min(dp[n - 1], dp2[n - 1]), dp3[n-1]); System.out.println(answer); } }이 후 위에서 예로 들었던 테스트 케이스를 실행해보았더니 답도 예측과 다르게 나오는데다가, 세번째 선택지 직전에 결국 똑같이 최솟값인 1을 고르게 되므로 의미가 없는 풀이였다는 것을 깨달았다. 따라서 다른 풀이 방법을 찾아야 했다.(그리고 이것도 아무리 봐도 백트래킹 문제로 보인다..)
정답풀이
고민 끝에 바킹독 선생님의 풀이를 보았다.
해답은 위 처럼 각 단계에서 가능한 최솟값 하나만 저장하는게 아니라, R G B 모두 각각 가능한 최솟값들을 다 저장하는 것이다.import java.io.*; import java.util.*; public class Main{ public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[][] dp = new int[n][3]; //점화식 //점화식을 생각한다기보다 dp테이블을 어떻게 채울지 //매 단계에서 r,g,b의 최솟값 저장 //dp[n][r] = min(dp[n-1][g], dp[n-1][b]) + r //dp[n][g], dp[n][b]도 마찬가지 //초기값 설정 StringTokenizer st = new StringTokenizer(br.readLine()); dp[0][0] = Integer.parseInt(st.nextToken()); dp[0][1] = Integer.parseInt(st.nextToken()); dp[0][2] = Integer.parseInt(st.nextToken()); for(int i = 1; i < n; i++){ st = new StringTokenizer(br.readLine()); int r = Integer.parseInt(st.nextToken()); int g = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + r; dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + g; dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + b; } int min = Math.min(Math.min(dp[n-1][0], dp[n-1][1]), dp[n-1][2]); System.out.println(min); } }이 문제를 풀어보니 점화식이라고만 생각하기보다 dp테이블을 어떻게 채울지, 즉 어떤 정보들을 메모이제이션해야 할까 라는 접근이 필요한 것 같다.
금융IT 개발자