다이나믹 - 설탕 배달

문제

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

분석/설계

입력 숫자의 범위가 3~5000 이기때문에 다이나믹 프로그래밍으로 풀지 않고

그리디 알고리즘으로 푸는 방법도 있을 것 같습니다.

하지만 다이나믹을 프로그래밍 사용하여 풀어봤습니다.

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

4, 7 같은 경우 3이나 5로 정확히 나눠서 떨어지지 않기때문에 문제의 조건대로 -1을 출력해야 하므로

이에 대한 예외 처리를 주의해야합니다.

 

dp[i] = min(d[i-3], d[i-5]) + 1 

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int dp[] = new int[N+1];

        dp[3] = 1;
        if(N == 4) {
            System.out.println(-1); 
            return;
        }
        if(N>4) dp[5] = 1;	

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

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

정리

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

이 문제는 점화식을 만들고 바텀업 방식으로 풀었고

편한 풀이 방식을 적용하면 될 것 같습니다.

참고

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