DP :: 백준 :: RGB거리 :: 1149

RGB거리 1149

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

[풀이방법]

dp[0][i] = i번째에 R을 칠할 때 까지 든 최소비용

dp[1][i] = i번째에 G을 칠할 때 까지 든 최소비용

dp[2][i] = i번째에 B을 칠할 때 까지 든 최소비용

이라고 할 때

dp[0][i] = min(dp[1][i-1], dp[2][i-1])+i번째 R을 칠할때 드는 비용

dp[1][i] = min(dp[0][i-1], dp[2][i-1])+i번째 G을 칠할때 드는 비용

dp[2][i] = min(dp[1][i-1], dp[0][i-1])+i번째 B을 칠할때 드는 비용

dp[0][i], dp[1][i], dp[2][i] 중 최솟값을 출력하면 된다.

import java.io.*;
public class Main {
 
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        int[][] ar = new int[3][num+1]; 
        String[] tmp1, tmp2;
        tmp1 = br.readLine().split(" ");
        ar[0][1] = Integer.parseInt(tmp1[0]);
        ar[1][1] = Integer.parseInt(tmp1[1]);
        ar[2][1] = Integer.parseInt(tmp1[2]);
        for(int i=2;i<=num;i++){
            tmp2 = br.readLine().split(" ");
            ar[0][i] = Math.min(ar[1][i-1], ar[2][i-1])+Integer.parseInt(tmp2[0]);
            ar[1][i] = Math.min(ar[0][i-1], ar[2][i-1])+Integer.parseInt(tmp2[1]);
            ar[2][i] = Math.min(ar[1][i-1], ar[0][i-1])+Integer.parseInt(tmp2[2]);
        }
        System.out.println(Math.min(ar[0][num], Math.min(ar[1][num], ar[2][num])));
    }
}

>>추가

2차원배열로 풀었는데 1차원배열로 푸는것도 가능할 것 같다.

dp[0] : i번째를 R로 칠했을 때 최솟값

dp[1] : i번째를 G로 칠했을 때 최솟값

dp[2] : i번째를 B로 칠했을 때 최솟값

모든 연산 마친 후 

min(dp[0], dp[1], dp[2]) 출력