백준 1149번 RGB거리(자바) - DP

RGB거리 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

61297

29580

22050

48.293%

문제

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

예제 입력 1 

3 26 40 83 49 60 57 13 89 99

예제 출력 1 

96

---

이 문제는 생각하는데 조금 오래 시간이 걸렸다. 

풀이 : i번째 집까지 칠하는 데 드는 비용의 최소값은 i+1번째 집까지 칠하는 데 드는 비용의 최솟값을 구하는 데

사용되지 않는다. 즉 각 집의 가능한 rgb 비용의 최소값을 사용해도 원하는 결과가 나오지 않는다는 것이다.

이 문제는 각 집에서 빨간색을 골랐을 때, 초록색을 골랐을 때, 파란색을 골랐을 때 드는 최소 비용을 모두 구한 후

비교하여 가장 작은 값을 출력하면 된다.

주어진 예제 입력을 예로 들어보면 다음과 같이 각 집에서 R, G, B 중 하나를 골랐을 때 드는 최소 비용을 표로 나타낼 수 있다.

R	G	B
26	40	83
49 minCost[1][0] = Min(40, 83) + 49	60 minCost [1][1] = Min(26, 83) + 60	57 minCost [1][2] = Min(26, 40) + 57
13 minCost[2][0] = Min(minCost[1][1], minCost[1][2]) + 13	89 minCost[2][1] = Min(minCost[1][0], minCost[1][2]) + 89	99 minCost[2][2] = Min(minCost[1][1], minCost[1][0]) + 13

보라색 글자는 예제에서 주어진 색을 칠하는 비용이고 minCost가 각 색을 골랐을 때 그 집까지 칠하는 데 드는 최소 비용을 나타낸다.

이렇게 모든 집, 모든 색에 대하여 드는 비용을 계산한 후

마지막 n번 집의 각 R, G, B 색의 minCost를 비교하여 가장 작은 값을 출력하면 된다.

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Test {

    static int n;
    static int[][] rgbCost;
    static int[][] minCost;
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        rgbCost = new int[n][3];
        minCost = new int[n][3];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 3; j++) {
                rgbCost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        for (int i = 0; i < 3; i++) {
            minCost[0][i] = rgbCost[0][i];
        }
        System.out.println(countMinCost());
    }
    static int countMinCost() {
        for (int i = 1; i < n; i++) {
            minCost[i][0] = Math.min(minCost[i-1][1], minCost[i-1][2]) + rgbCost[i][0];
            minCost[i][1] = Math.min(minCost[i-1][0], minCost[i-1][2]) + rgbCost[i][1];
            minCost[i][2] = Math.min(minCost[i-1][1], minCost[i-1][0]) + rgbCost[i][2];
        }
        return Math.min(Math.min(minCost[n-1][0], minCost[n-1][1]), minCost[n-1][2]);
    }
}