[백준/Java] 1149번. RGB 거리

728x90

문제

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번집	26	40	83
2번집	49	60	57
3번집	13	89	99

 

그렇게 되면,

1번집 - 빨강26

2번집 - 파랑57

3번집 - 빨강13 을 칠하게 됩니다. -> 96

 

다른 경우를 살펴볼까요?

	빨강	초록	파랑
1번집	10	14	83
2번집	49	60	57
3번집	70	100	5

1번집 - 빨강 10

2번집 - 파랑 57

3번집 - 빨강 70 (이전 집이 파랑이므로 빨강, 초록 중 최소 cost 선택)

이 경우, 총 비용은 137이 됩니다.

 

하지만 실제 최소 비용은 68입니다.

1번집 - 초록 14

2번집 - 빨강 49

3번집 - 파랑 5

 

따라서 이 문제는, 모든 선택할 수 있는 경우 중에서 색상 비용이 최소값이 되는 경우를 찾아야합니다.

 

3번집 빨강색으로 칠한다고 하면, (2번집 초록색 + 3번집 빨강색)으로 칠한 비용과 (2번집 파랑색 + 3번집 빨강색)으로 칠한 비용의 최소값을 선택해주어야 합니다. 

 

여기서 또, 2번집을 초록색으로 칠한다고 하면 (1번집 빨강색 + 2번집 초록색)으로 칠한 비용과 (1번집 파랑색 + 2번집 초록색)으로 칠한 비용의 최소값을 선택해주어야 합니다. 

 

따라서 이 부분은 재귀 호출이 필요합니다.

 

이후, 해당 집을 칠하는 비용의 최소값은 dp에 저장해둡니다.

 

 

Top_down

import java.util.*;
import java.io.*;

public class Main {
    
    static int[][] cost;
    static int[][] dp;

    static int paint(int x, int color) {
        if (dp[x][color] > 0) {
            return dp[x][color];
        }

        if (color == 0) { //Red
            dp[x][0] = Math.min(paint(x-1,1), paint(x-1,2)) + cost[x][0];
        } else if (color == 1) { //Green
            dp[x][1] = Math.min(paint(x-1,0), paint(x-1,2)) + cost[x][1];
        } else { //Blue
            dp[x][2] = Math.min(paint(x-1,0), paint(x-1,1)) + cost[x][2];
        }
        return dp[x][color];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int size = Integer.parseInt(br.readLine());
        cost = new int[size][3]; //색상 비용
        dp = new int[size][3]; //최소 비용

        for (int i = 0; i < size; i++) {
            StringTokenizer tk = new StringTokenizer(br.readLine());
            cost[i][0] = Integer.parseInt(tk.nextToken());
            cost[i][1] = Integer.parseInt(tk.nextToken());
            cost[i][2] = Integer.parseInt(tk.nextToken());
        }

        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

        int red = paint(size - 1, 0);
        int green = paint(size - 1, 1);
        int blue = paint(size - 1, 2);
        int minCost = Math.min(red, Math.min(green, blue));

        System.out.println(minCost);
    }
}

 

Bottom-up

package boj.Silver;

import java.io.*;
import java.util.*;

public class Main {

    static int[][] cost;
    static int[][] dp;

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int size = Integer.parseInt(br.readLine());
        cost = new int[size][3];
        dp = new int[size][3];

        for (int i = 0; i < size; i++) {
            StringTokenizer tk = new StringTokenizer(br.readLine());
            cost[i][0] = Integer.parseInt(tk.nextToken());
            cost[i][1] = Integer.parseInt(tk.nextToken());
            cost[i][2] = Integer.parseInt(tk.nextToken());
        }

        dp[0][0] = cost[0][0];
        dp[0][1] = cost[0][1];
        dp[0][2] = cost[0][2];

        for (int i = 1; i < size; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
        }
        int minCost = Math.min(dp[size-1][0], Math.min(dp[size-1][1], dp[size-1][2]));
        System.out.println(minCost);
    }
}