[23/05/12] B2839_DP

2박3일 예비군 다녀오느라 공부를 못했다... ; - ;

package baekjoon;

import java.util.Scanner;

public class B2839_DP {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int dp[] = new int[5001]; // 0 제외하고 1 부터 5001 까지

        for(int i=0; i<8; i++) {
            if(i==3 || i==5) {
                dp[i] = 1;
            } else if(i==6) {
                dp[i] = 2;
            } else {
                dp[i] = -1;
            }
        }

        for(int i=8; i<=N; i++) {
            if(dp[i-5] != -1 && dp[i-3] != -1) {
                dp[i] = 1 + Math.min(dp[i-5], dp[i-3]);
            } else if(dp[i-5] != -1 && dp[i-3] == -1) {
                dp[i] = 1 + dp[i-5];
            } else if(dp[i-5] == -1 && dp[i-3] != -1) {
                dp[i] = 1 + dp[i-3];
            }
        }

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

 

느낀점

설탕봉지가 3kg짜리, 5kg짜리가 주어졌으니 8kg 전까지 최소 설탕봉지 개수를 직접 구해본다

7kg까지 구하는 이유는 당연히 8kg는 3kg+5kg 해서 최소 2봉지일 것이 당연하기 때문이다.

7kg까지 직접 구해봤을 때 구해진 설탕봉지의 개수는 최소이다.

8kg부터 다음과 같은 점화식으로 풀면 최소 봉지개수를 구할 수 있다.

dp[ i ] = 1 + Math.min( dp[ i + 3 ], dp[ i + 5 ] )

 

이것이 동적 프로그래밍, DP 이다.

DP[  ]

만약 설탕의 무게가 5000kg였다면 dp[ 5000 ] 까지 하나하나 최소 설탕봉지 개수를 파악하고 배열을 채워나갈건가?

너무 비효율적이다.

dp[ 7 ] 까지만 최소 설탕봉지 개수를 파악하고 배열을 채워나가기만 하면 dp[ 8 ] 부터는 점화식으로 풀면 된다!

 

DP란,

복잡한 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 기법이다.

중복되는 부분 문제를 한번만 계산하고 그 결과를 저장하여 중복 계산을 피하는 특징을 갖는다.