백준 1149. RGB거리 :: 돼지개발자

출저 : https://www.acmicpc.net/problem/1149

"DP"

어려웠다. 기초적인 dp문제라고 했는데 왜 이리 어려웠지...ㅎㅎ 

dp[x] = dp[x-1] + min(x) ; 까지는 생각을 하고, 해답을 봤다. 그리고 최초 dp[0] 가 R,G,B 일 때를 모두 체크하기위해 dp[x][3] 배열을 만들어 해당 dp 값을 이용한다.

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

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Main {       static int N;     static int[][] map;     static int[][] dp;          public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));                  N = Integer.parseInt(br.readLine());                  dp = new int[N][3];         map = new int[N][3];                  for (int i = 0; i < N; i++) {             StringTokenizer st = new StringTokenizer(br.readLine());             map[i][0] = Integer.parseInt(st.nextToken());             map[i][1] = Integer.parseInt(st.nextToken());             map[i][2] = Integer.parseInt(st.nextToken());         }                  for (int i = 0; i < 3; i++) {             dp[0][i] = map[0][i];         }                  // 지점 j 에서 R,G,B 를 넣었을 때 최소값을 갱신한다.         for (int j = 1; j < N; j++) {             dp[j][0] = Math.min(dp[j-1][1], dp[j-1][2]) + map[j][0];             dp[j][1] = Math.min(dp[j-1][0], dp[j-1][2]) + map[j][1];             dp[j][2] = Math.min(dp[j-1][0], dp[j-1][1]) + map[j][2];         }           int min = Integer.MAX_VALUE;         for (int i = 0; i < 3; i++) {             min = Math.min(min,dp[N-1][i]);         }         System.out.println(min);     } }   Colored by Color Scripter

cs