[알고리즘] 백준 1149 RGB거리 -dp-

 

 

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

1149번: RGB거리

 

첫 dp(다이나믹 프로그래밍 또는 동적계획법) 문제를 풀어봤습니다. 단계별 풀기에서 풀었는데 이전단계들을 생략하고 이 문제부터 풀었네요 ㅎㅎ

 

먼저 DP의 개념은 다음과 같습니다.

Dynamic Programming; DP

특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계 기법이다.

조금 장난스럽게 말해서 답을 재활용하는 거다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고...엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다. 동적 계획법은 "어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는" 방식의 알고리즘을 총칭한다.

답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야하는 류의 문제의 구조를 Optimal Substructure라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다.

경제학에서는 성장 모형 등을 계산하는데 자주 쓰인다. 이 때는 컴퓨터 그딴 거 없고 손으로 푼다. 석기시대

동적 계획법을 영문으로는 다이나믹 프로그래밍(dynamic programming)이라 표기하는데, 이름과는 달리 딱히 다이나믹하지도 않고 프로그래밍이라는 단어와도 큰 연관이 없다.[1][2] 이에 대해 이광근 교수의 저서 "컴퓨터 과학이 여는 세계"에서는 다이나믹 프로그래밍을 본질적인 의미를 더 살려서 기억하며 풀기로 더욱 적절하게 번역하였다.

 

 

이번 문제의 경우 DP 문제이기 때문에 개념 그대로 과거에 구한 해를 활용하는 방법을 사용했습니다.

집을 R G B 의 색으로 칠할 수 있는데 연속된 색으로 칠하면 안되고 최소비용을 구해야합니다.

현재 N번째 집을 R로 칠할 경우 이전 N-1 집은 G B 의 색일테고 이 중 최소비용을 택했을 것 입니다. 그러므로 N-1 집 색의 G B 중 최소비용과 현재 집의 R 비용을 더해 주어 N번째 집까지의 최소비용이 누적되면서 구해집니다.  G B도 같은 방식이므로 설명을 생략하겠습니다.)

이후 N+1 집의 색을 구할때도 R색을 칠하는 경우 마찬가지로 N번째 까지의 G B의 색 중 최솟값 비용과 현재 N+1집의 R을 더한 누적금액을 저장해줍니다. 즉 한마디로 정리하면 현재 집은 이전 집과 다른색을 칠해야하며 이전 집들에는 과거의 최소 누적비용을 담고 있습니다. 그래서 현재 색칠할 집을 과거와 다른 색 && 최소비용이였던 색으로 칠해주면 됩니다. 당연히 현재집 페인트 가격과 누적금액 계속 쌓아주고요  (

그래서 마지막에는 결국 3가지의 최소비용이 나오게되며 그 중 가장 최솟값이 답이 됩니다. 

 

말로 풀려니 먼가 꼬이네요...

 

코드는 다음과 같습니다.

import java.util.Scanner;

class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] R = new int[N + 1];
        int[] G = new int[N + 1];
        int[] B = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            R[i] = sc.nextInt();
            G[i] = sc.nextInt();
            B[i] = sc.nextInt();
        }
        for (int i = 1; i < N; i++) {
            R[i + 1] += Math.min(G[i], B[i]);
            G[i + 1] += Math.min(R[i], B[i]);
            B[i + 1] += Math.min(R[i], G[i]);
        }
        System.out.println(Math.min(Math.min(R[N], G[N]), B[N]));
    }


}