[백준 *Java] - RGB 거리 (1149)

 

RGB 거리 문제보기

1149번: RGB거리

문제 설명
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 보다 작거나 같은 자연수이다.

 

DP로 접근을 하려하는데, 이번 문제는 1, 2, 3 더하기5 문제와 유사합니다.

DP 테이블 안에는 최소합으로 이루어진 값들이 합해지면서 부분문제를 저장할 것입니다.

이 문제는 초기화를 해줄 필요가없는 문제니,

바로 로직을 구현하여 문제를 풀어볼 생각입니다.

일단 RGB 숫자를 1,2,3으로 생각을하고,

여러 테스트케이스 중, 예제 입력5를 기준으로 일단 최소합이 어떻게 합쳐지는 지 알아보자,

253 이라는 출력 값을 갖기위해서는

39 -> 32 -> 63 -> 29 -> 11 -> 13 -> 47 -> 19 이렇게 수가 합해져야 합니다.

위의 합을 보면, RGB에서 제일 작은 수를 최소합으로 합해진 건 아닙니다.

색이 칠해진 수는 제일 작은 수가 아니지만, 다음에 올 수에서 작은 수를 택하기 위해서 전략적으로 선택된 값입니다.

결과적으로는, 뒤의 수까지 고려해야합니다. 

두번 째에 합한 수 122-> 127로 수정되어야 합니다. (오타)

 

R -> G, B 중 최소값과 합해지며 그 값을 DP테이블에 담기 

G -> R, B 중 최소값과 합해지며 그 값을 DP테이블에 담기 

B -> R, G 중 최소값과 합해지며 그 값을 DP테이블에 담기

 

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

public class Boj_1149 {

    static int [][] DP;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int ordCnt = Integer.parseInt(br.readLine());
        DP = new int[ordCnt+1][4];

        for (int i = 1; i <= ordCnt;i++) {
            StringTokenizer 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][1] = R + Math.min(DP[i-1][2], DP[i-1][3]);
            DP[i][2] = G + Math.min(DP[i-1][3], DP[i-1][1]);
            DP[i][3] = B + Math.min(DP[i-1][1], DP[i-1][2]);
        }
        System.out.println(Math.min(DP[ordCnt][3],Math.min(DP[ordCnt][1], DP[ordCnt][2])));
    }
}