[백준, DP] 1149 RGB 거리

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

 

 

DP 문제를 볼때마다 풀 수 있을 것 같았지만 역시나 ㅎ.. 잘 안된다. 점화식을 잘 만들었다 생각했으나 오산이었다.

 

기존 

$$ a_{n} = a_{n-3} + min(a_{n-2}, a_{n-1})$$ 

 

처음에는 3개의 집이 서로 다른 색이어야하는 것으로 이해했다.

그래서 누적합으로 저장한 뒤, 연속 3개의 색이 올 수 없기에 무조건 3번째마다 같은 색이 올 것이라고 생각하고 위와 같은 점화식을 생각했었다.

 

잘못된 점화식이었다.

개선

점화식을 고민하다 결국 찾을 수 없어서 다른 분들의 풀이를 참고했다.

정답을 확인한 이후, 내가 잘못 이해했다는 것을 인지했다.

 

정답은 n번째 집의 색에 따라 이전 n-1 번째 집의 남은 2개의 색에 대한 경우의 수들 중, 최솟값을 반영하면 되는 것이었다.

N번째 집을 칠할 색을 A라고 하고 그렇다면 남은 2개의 색을 각각 B, C라고 가정한다면 점화식은 이와 같다.

(A,B,C라는 색들에 대한 별도의 Index를 선언해둔 상황이다.)

 

dp[N][A] = min( dp[N-1][B], dp[N-1][C] ) + value(A)

 

물론, B,C를 선택한 경우는 A 대신 B와 C를 넣으면 된다.

 

위 점화식을 코드로 표현하면 이와 같다.

 

public static void main(String[] args) throws Exception{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());
    int[][] dp = new int[N+1][3];       // 1 : red, 2 : green, 3 : blue

    for (int i = 1; i <= N; i++) {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int red = Integer.parseInt(st.nextToken());
        int green = Integer.parseInt(st.nextToken());
        int blue = Integer.parseInt(st.nextToken());

        dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + red;
        dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + green;
        dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + blue;
    }

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

 

느낀 점

ㅎ.. DP 문제를 더 풀자. 질문을 명확히 이해해야하고 DP에 대한 감을 키우자.