[백준 알고리즘] 1149번(RGB거리) - 관련 : DP문제

백준 알고리즘

오늘 풀어본 문제는 다이나믹 프로그래밍과 관련된 문제입니다.

알고리즘이 아직 생소해서 그런지 문제를 이해하는데 시간이 걸렸습니다.

특히 오늘은 어이없는 실수를 했습니다. 어떤 실수를 했는지는 밑에 있습니다.

참 부끄럽네요 이런 실수는.... 

  동적 계획법(Dynamic Programming)

혹시나 아직 개념을 모르시는 분이 있을까봐 설명을 드립니다.

일반적으로 문제를 여러 개의 하위 문제로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것입니다.

각 하위 문제의 해결을 계산하고 그 계산 값을 다른 곳에 저장해 두었다가 같은 문제가 나왔을 경우 저장된 값을 가지고와서 불필요한 것들을 줄이고 계산을 빨리 할 수 있도록 도와줍니다.

더 자세한 내용은 이 곳에서 확인 하세요

(출처 : 위키 백과)

  문제

  해설

문제를 완벽하게 이해를 하고 나면 금방 해결할 수 있는 문제입니다.

문제 해결을 위해 문제를 그림으로 한번 나타내 보겠습니다.

우리는 이것을 통해 가장 싸게 비용을 처리하는 방법을 구해야 합니다.

아래의 그림은 만약 첫 번째 페인트를 레드로 칠했다면 그 다음 번에 올 수 있는 경우의 수를 나타낸 것 입니다

JIMMY는 3번지 -> BLUE(40) / 2번지 -> GREEN(20) / 1번지 -> RED(20) 구입

RAIN은   3번지 -> GREEN(50) / 2번지 ->BLUE(10) / 1번지 -> RED(10) 구입

각각 번지에 맞게 구매한 페인트 색과 가격입니다. 

이렇게 되었을 경우 JIMMY는 총 80불을 사용했고 RAIN의 경우 70불을 사용했습니다. 

우리는 이럴 경우 RAIN의 경우처럼 최소의 비용을 구하는 것입니다.

우리는 이것을 식으로 나타낼 수 있습니다.

list[빨강] = MIN(list[초록] , list[파랑]) + 빨강 비용 이 됩니다.

이 말은 1번지 / 2번지만 보고 예를 들게 되면 

최솟값을 구하기 때문에 초록과 파랑 중에 더 적은 값을 가지고 와야하고 그 값을 빨강의 비용과 합하면 우리는 최솟값을 구할 수 있습니다. 이해 되시나요?

빨강이 기준이 되어서 그렇지 우리는 초록 / 파랑의 경우도 모두 구해야합니다. 

최솟값이 어떤 값이 될지 모르기 때문이죠 위에 JIMMY 와 RAIN 처럼 말이죠

처음 JIMMY와 RAIN 은 3번지에서 JIMMY가 더 낮은 가격으로 페인트를 구매했습니다. 하지만 결과론적으로 RAIN이 더 적은 금액으로 페인트를 구매했으니까요

이것만 이해 된다면 그냥 다 끝이 난겁니다. 

코드로 넘어가기 전에 제가 실수를 하나 했었습니다.

저는 여기서 빨강 / 파랑 / 초록 이렇게 무조건 색이 다른 걸로 칠해야한다고 생각을 했습니다.

문제를 제대로 읽지 않은 거조 멍청한거죠 그래서 문제를 이해하는데 좀 걸렸습니다. 

여러분은 이런 실수 안하시겠지만 혹시나 하는 마음에 적었습니다.

  코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Beak1149 {
 
    private static int R = 0;
    private static int G = 1;
    private static int B = 2;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        int n = Integer.parseInt(br.readLine());// 집 갯수
        int[][] list = new int[3][n + 1];
        int r, g, b = 0;
        int i;
        for (i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            r = Integer.parseInt(st.nextToken());
            g = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
 
            list[R][i] = Math.min(list[G][i - 1], list[B][i - 1]) + r;
            list[G][i] = Math.min(list[R][i - 1], list[B][i - 1]) + g;
            list[B][i] = Math.min(list[R][i - 1], list[G][i - 1]) + b;
 
        }
        int result = Math.min(list[R][n], Math.min(list[G][n], list[B][n]));
 
        System.out.println(result);
 
    }
}