[BOJ] 백준 1149 RGB거리

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

 Input 

3

26 40 83

49 60 57

13 89 99

 

 Output 

96

▶ 동적계획법(Dynamic Programming, DP) 

동적계획법(Dynamic Programming, DP)

3개의 집에 R - B - R일 때, 최소 비용

26     40     83

49     60     57

13     89     99

→ 26 + 57 + 13 = 96

 

Sample Case

1 2 2

1 2 2

2 1 3

→ 2 + 1 + 1 = 4

 

i 번째 집에서 칠하는 색깔은 다음과 같다.

① R[i] 선택, 이전 단계에서 G[i-1] or B[i-1]이 선택

     → R[i]+G[i-1], R[i]+B[i-1] 중 최솟값

② G[i] 선택, 이전 단계에서 R[i-1] or B[i-1]이 선택 

    → G[i]+R[i-1], G[i]+B[i-1] 중 최솟값

③ B[i] 선택, 이전 단계에서 R[i-1] or G[i-1]이 선택 

    → B[i]+R[i-1], B[i]+G[i-1] 중 최솟값

마지막 n 번째에서 ①, ②, ③ 중 최솟값 출력

 

[N = 3에 대한 시뮬레이션] 

[i = 1]

1 2 2

    

[i = 2]    

1 2 2    → 이전 단계 누적 값

1 2 2    

→ 1 선택, 이전 단계에서 2 2 선택 → min(1+2, 1+2)  = 3

→ 2 선택, 이전 단계에서 1 2 선택 → min(2+1, 2+2)  = 3

→ 2 선택, 이전 단계에서 1 2 선택 → min(2+1, 2+2)  = 3

[i = 3]

3 3 3    → 누적값

2 1 3    

→ 2 선택, 이전 단계에서 3 3 선택 → min(2+3, 2+3)  = 5

→ 1 선택, 이전 단계에서 3 3 선택 → min(1+3, 1+3)  = 4

→ 3 선택, 이전 단계에서 3 3 선택 → min(3+3, 3+3)  = 6

▶ min(5, 4, 6) = 4 

 

코드 분석

① n > 0 이므로 색깔별 비용으로 초기화

② 2번째 집부터 n 번째 집까지

③ 이전 집까지 최소비용을 누적

④ i번째 집에서 각각의 색으로 칠했을 때 최소 비용 도출

⑤ n번째 집에서 R, G, B를 칠하는 경우 중 최솟값 출력

* 작은단계부터 분석하는 것이 DP 핵심.

 

---

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());

        int[] R = new int[n];
        int[] G = new int[n];
        int[] B = new int[n];

        for (int i = 0; i < n; i++) {
            R[i] = Integer.parseInt(sc.next());
            G[i] = Integer.parseInt(sc.next());
            B[i] = Integer.parseInt(sc.next());
        }
    // 초기값으로 각각의 색만 선택한 것으로 저장
        int choiceR = R[0], choiceG = G[0], choiceB = B[0];
        
        for (int i = 1; i < n; i++) {

            int cumulativeR = choiceR, cumulativeG = choiceG, cumulativeB = choiceB;

            choiceR = R[i] + minOfValues( cumulativeG , cumulativeB );
            choiceG = G[i] + minOfValues( cumulativeR , cumulativeB );
            choiceB = B[i] + minOfValues( cumulativeR , cumulativeG );
        }

        System.out.println(minOfValues(choiceR, choiceG, choiceB));

    }

    private static int minOfValues( Integer... arr ) {
        int min = 0;
        if (arr.length > 0) {
            min = arr[0];
        }

        for (int i = 1; i < arr.length; i++) {
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        return min;
    }
}