백준 - 설탕배달 [dp]

public class P2839 {
    static int[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        solution(n);
    }

    /**
     * dp 풀이 참조
     */
    private static void solution(int n) {
        dp = new int[n + 1];

        if (n >= 3){
            dp[3] = 1;
        }

        if (n >= 5){
            dp[5] = 1;
        }

        for (int i = 6; i <= n; 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;
                }
            }
        }

        if (dp[n] == 0){
            System.out.println("-1");
            return;
        }

        System.out.println(Arrays.toString(dp));

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

DP풀이를 참고하였고, DP의 개념을 가져가보자!

1, 우선 dp배열을 static으로 선언해줍니다.
2, dp[3]과 dp[5]에 1값을 먼저 넣어줍니다.
3, 6이상 부터 n번까지 dp배열을 채워주기 위하여 for문을 순회합니다.
4, i % 3일 경우 dp[i - 3]의 값을 가져와 +1 하여 새로운 dp[i]에다 넣어줍니다.
예를 들어, i = 6이라고 한다면 [0, 0, 0, 1, 0, 1, 0] dp배열이 이렇게 있을텐데 dp[i - 3]은 dp[3]의 값인 1을 가져오고 +1을 더 해주어 dp[6] = 2의 값이 들어가게 됩니다. (5도 같은 로직)
5, if (dp[i - 3] != 0 && dp[i - 5] != 0)는 3과 5로 나눠지지 않는 값, 즉 3과 5를 적절히 빼줘야하는 경우입니다.
예를 들어, ㅑ = 8일 경우 3과 5로는 나눌 수 없어 dp[8 - 3] 의 값과 dp[8 - 5] 의 값이 0이 아니라면 둘의 값중 min을 통해 최소 값을 가지고와 +1을 해줍니다.
6, 이렇게 dp문이 다 채워진다면 dp[n]을 통해 값을 출력하고 만약에 dp[n] == 0 이라면 그 값은 봉지를 전달할 수 없는 값이기 때문에 -1을 리턴해줍니다.

나의 풀이

    private static void solution(int n) {
        int count = 0;

        while (n != 0){
            if (n % 5 == 0){
                count += n / 5;
                n %= 5;
            } else {
                // 값이 나오지 않을 경우
                if (n < 3){
                    break;
                }
                n -= 3;
                count++;
            }
        }

        if (n != 0){
            count = -1;
        }

        System.out.println(count);
    }

1, 5로 최대한 나누기로 했다.
2, 5로 나눠지지 않을 경우 else문을 통해 n -= 3을 계속 해준다.
3, n = 0이 된다면 while문을 나가고, else문안에서의 if문을 통해 n이 3보다 작아진다면 더 이상 정답이 될 수 없기 때문에 break문을 통해 나간다.
4, n 값이 0이 아니라면 count에 -1을 넣어준다.