다이나믹프로그래밍 - RGB 거리

문제

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

분석/설계

입력 숫자의 범위가 2~1000 이므로 다이나믹 프로그래밍으로 풀어봤습니다.

점화식을 아래와 같이 만들어봤습니다. 

 

dp[N][0] = min( dp[N-1][1], dp[N-1][2] ) + dp[N][0]

dp[N][1] = min( dp[N-1][0], dp[N-1][2] ) + dp[N][1]

dp[N][2] = min( dp[N-1][0], dp[N-1][1] ) + dp[N][2]

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int arr[][] = new int[N+1][3];
        int dp[][] = new int[N+1][3];

        for (int i=1; i<=N; i++) {
            for (int j=0; j<3; j++) {
                arr[i][j] = scanner.nextInt(); 
            }
        }

        for (int i=1; i<=N; i++) {
            dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
            dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
            dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
        }

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

정리

다이나믹 프로그램은 탑다운과 바텀업 방식이 있습니다.

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고, 문제만 보고 점화식이 잘 정의가 안되면

예시를 여러 개 만들고 패턴을 찾아내어 점화식을 만들고 알고리즘을 적용하여 코드를 작성하면 

수월합니다.

참고

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