[백준] 1149 - RGB 거리 java 문제 풀이

1. 문제 설명

문제 링크

(1) 1~N번까지의 집이 있음. 이 집들을 빨강, 초록, 파랑으로 색칠하려고 함.
(2) 집은 인접한 번호와 색깔이 달라야 함.
예를 들어 1번 집은 2번집과 색깔이 달라야 함. i번 집은 i-1번 집과 i+1번 집과 색깔이 달라야 함.
(3) 각 집을 빨강, 초록,파랑으로 칠했을 때의 비용이 주어질 때, 조건에 맞도록 칠한 최소 비용을 구하라.

2. 접근 방식

KEY WORD: DP

해당 문제는 생각할 것이 많이 없는 DP 문제이다.
N행 3열의 DP 배열을 만든다. 0행은 빨강, 1행은 초록, 3행은 파랑에 해당하는 행이다. 그렇다면 각 배열의 원소는 무엇을 뜻할까?
만약 dp[i] [2] 라면 i번째 집을 초록으로 칠했을 때의 최소 비용 이다.
dp[3] [0] 은 3번째 집을 빨강으로 칠했을 때의 최소 비용 이다.

이를 어떻게 구할까?
dp의 메모이제이션을 사용하면 된다. 메모이제이션이란, 이전 정보를 저장해서, 불필요한 중복 계산을 제거하는 방법이다. 여기서는 i번째 집을 빨강, 초록, 파랑 으로 칠했을 때의 최소 비용 정보를 저장해둬서, 다음 i+1번째 집을 칠할 때 최소 비용은 이전 집을 모두 돌아볼 필요 없이, i번째 집을 칠할 때의 최소비용만을 이용해서 구할 수 있게 하는 것이다. 우리는 이를 통해, loop문 한 번만으로 문제의 답을 구할 수 있다. 다음 예시를 보자.

메모이제이션을 이용해 이전 정보를 계속 활용하기 위해선 이전 정보와 현재 정보간의 공식이 필요하다. 이것을 점화식이라고 한다. 위의 사진은 1번 집을 각 색깔로 칠했을 때의 최소비용이다. 그러면 2번째 집을 각 색깔로 칠했을 때의 최소비용은 어떻게 되는가?
빨강 집 = 2번째 집을 빨강색으로 칠한 비용 + 1번 집을 초록색으로 칠했을 때랑, 파랑색으로 칠했을 때의 최소값
초록 집 = 2번째 집을 초록색으로 칠한 비용 + 1번 집을 빨강색으로 칠했을 때랑, 파랑색으로 칠했을 때의 최소값
파랑 집 = 2번째 집을 파랑색으로 칠한 비용 + 1번 집을 빨강색으로 칠했을 때랑, 초록색으로 칠했을 때의 최소값
이다. 그림으로 표현하면 다음과 같다.

그럼 3번째 집은 어떤가?
3번째 집 또한 3번째 집을 특정 색깔로 칠했을 때의 비용 + 이전 집을 다른 색깔로 칠한 경우 중 최소 비용 이다.
3번째 집에서의 최소 비용을 구할 때, 1 번째 집까지 조회할 필요가 없는 것이, 이미 2번째 집에서 1~2번까지 다 고려한 최소 비용으로 값을 구해놓았기 때문이다. 따라서 dp 배열의 2번째 집 계산 값들만 보면 된다. 또 구해보면 이렇게 된다.

이제 점화식을 구해보자. 점화식은

dp[i][0] = i번째 집을 0번 색깔로 칠했을 때의 비용 + Math.min(dp[i-1][1], dp[i-1][2]);

이다. 물론 위의 식은 초록색으로 칠했을 때의 dp이고, 빨강색으로 칠할 때와 파랑색으로 칠할 때는 이전의 집과 색깔이 안 겹치도록 번호를 바꿔가며 점화식을 만들어주면 된다.

3. 코드 풀이

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

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

        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] = red + Math.min(dp[i-1][1], dp[i-1][2]);
            dp[i][1] = green + Math.min(dp[i-1][0], dp[i-1][2]);
            dp[i][2] = blue + Math.min(dp[i-1][0],dp[i-1][1]);
        }

        Arrays.sort(dp[N]);
        System.out.println(dp[N][0]);
    }
}