백준 알고리즘: 1149번 RGB거리

문제 정보

---

1149번: RGB거리

 

핵심

---

DP 알고리즘으로, 점화식을 어떻게 세우는지가 중요한 것 같음

해당 문제의 경우에는, 결국 이전 집의 색이랑 같지 않으면 되기 때문에

 

현재 위치에서 만약 빨간색(R)을 골랐다면?

dp[현재위치][빨간색 선택] = (dp[직전위치][파랑색 선택], dp[직전위치][초록색 선택]) 중 최소값 + 현재위치에서 빨간색을 선택할 때의 비용

이 된다

 

그러므로 이를 Java 언어로 점화식을 작성해 보면 (0: R, 1:G, 2:B)

dp[currentIndex][0] = Math.min(dp[currentIndex-1][1], dp[currentIndex-1][2]) + costMap[currentIndex][0];

다음과 같은데, 여기서 다음과 같이 3가지의 경우를 생각해 주어야 한다

dp[currentIndex][0] = Math.min(dp[currentIndex-1][1], dp[currentIndex-1][2]) + costMap[currentIndex][0];
dp[currentIndex][1] = Math.min(dp[currentIndex-1][0], dp[currentIndex-1][2]) + costMap[currentIndex][1];
dp[currentIndex][2] = Math.min(dp[currentIndex-1][0], dp[currentIndex-1][1]) + costMap[currentIndex][2];

왜냐하면, 현재까지의 최솟값이 미래에도 최솟값임을 보장해주지 않기 때문이다

현재 위치에서 R을 골랐을 때, 최솟값이라고 하더라도 다음 위치에서 R을 골라야만 최솟값을 만들 수 있다면?

현재 위치에서 선택한 색상은 다음 위치에서 선택할 수 없기에, 3가지 경우를 모두 고려해서 이를 풀이해 주어야 한다

 

풀이

---

//package solving;

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[][] costMap = new int[N+1][3];
        int[][] dp = new int[N+1][3];
        for(int currentIndex = 1; currentIndex<=N; currentIndex++) {
            String inputOneLine = br.readLine();
            StringTokenizer st = new StringTokenizer(inputOneLine);
            for(int rgb = 0; rgb<3; rgb ++) {
                costMap[currentIndex][rgb] = Integer.parseInt(st.nextToken());
            }
            dp[currentIndex][0] = Math.min(dp[currentIndex-1][1], dp[currentIndex-1][2]) + costMap[currentIndex][0];
            dp[currentIndex][1] = Math.min(dp[currentIndex-1][0], dp[currentIndex-1][2]) + costMap[currentIndex][1];
            dp[currentIndex][2] = Math.min(dp[currentIndex-1][0], dp[currentIndex-1][1]) + costMap[currentIndex][2];
        }

        System.out.println(Math.min(dp[N][0], Math.min(dp[N][1], dp[N][2])));
    }
}

사실 풀고 봤는데, costMap을 받아서 저장해 줄 필요가 없이 그냥 StringTokenizer로 분리된 3가지 정수를 그대로 사용해주기만 하면 되었던 것 같다

일단 이렇게 풀었으니, 다음과 같은 풀이를 생각해볼 수 있다 정도로 이해하면 좋을 듯 싶다

 

Source Code on GitHub

---