[백준 - 2839] 설탕배달 - Java

문제 설명

 

2839번: 설탕 배달

 

풀이 : Success

소스 코드

import java.util.Scanner;

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

        if (N >= 5) {
            result = N / 5;
            N %= 5;
            if (N % 3 == 0) {
                result += N / 3;
            }
            else {
                while (true) {
                    result -= 1;
                    N += 5;
                    if (N % 3 == 0) {
                        result += N / 3;
                        break;
                    }
                    if (sugar == N) {
                        result = -1;
                        break;
                    }
                }
            }
        }
        else if (N == 3) {
            result = 1;
        }
        else {
            result = -1;
        }

        System.out.println(result);
    }
}

 

풀이 회고

3개의 if 분기문을 이용하여 풀이했습니다.

 

첫번째 분기문은 설탕이 5 이상일 경우, 두번째 분기문은 설탕이 3인 경우, 세번째 문기문은 설탕이 4인 경우입니다.

 

설탕이 3인 경우는 결과값이 1이고, 설탕이 4인 경우는 결과값이 -1이므로 단순합니다.

 

하지만 설탕이 5 이상인 경우에는 그리디 알고리즘을 적용하여 풀 수 있었는데, (5로 나누어 떨어지는 경우는 단순)

 

문제에서 요구하는 최소의 봉지 개수를 충족시키기 위해 설탕을 5로 먼저 나누고 0으로 떨어지지 않으면 5를 하나씩 빼서 그 자리를 3으로 메우고자 했습니다.

 

최종적으로 N이 3으로 떨어지면 5와 3의 몫 값 합계를 출력시키도록 했고, 떨어지지 않는다면 -1을 출력시키도록 했습니다.

 

모범 코드

본 풀이는 개발하는 지토님의 기술블로그를 참고한 내용입니다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if(n < 5) {
            if(n == 3) System.out.println(1);
            else System.out.println(-1);
            return;
        }
        
        int memo[] = new int[n + 1];
        Arrays.fill(memo, 9999);
        memo[3] = 1;
        memo[5] = 1;
        for(int i = 6; i < memo.length; i++) {
            dp[i] = Math.min(memo[i - 3] + 1, memo[i - 5] + 1);
        }
        
        if(dp[n] > 9999) {
            System.out.println(-1);
        }
        else {
            System.out.println(dp[n]);
        }
    }
}

 

코드 분석

위 풀이 방법은 다이나믹 프로그래밍을 이용했습니다. 이때 n이 5미만일 경우 3일 때는 3으로 나누어 떨어져 1이 결과값이고, 나머지 경우에는 3이나 5로 나누어 떨어지는 게 없어 -1이 결과값입니다.

 

이후 메모라이징 기법을 이용하기 위한 n + 1 크기의 배열을 생성한 후 2000 값으로 초기화 시켜주었는데 이는 3이나 5로 떨어지는 수(3 <= n <= 5000)라면 2000 이상 나올 수 없기 때문에 임의로 설정한 값입니다. 즉, 어떤 결과값(메모라이징 기법을 통해 계산된 결과)이 2000 이상이라면 이는 3이나 5로 나누어 떨어지지 않는 수라는 것을 의미합니다.

 

5는 5로 나누어 떨어지므로 1입니다. 따라서 우리는 메모라이즈 초기값으로 memo[3] = 1, memo[5] = 1로 설정할 수 있습니다. 이후 6의 값(i)부터 for 반복문을 통해 메모라이징 기법으로 결과값을 구하고자 했습니다. 이때 3이나 5로 나누어 떨어지는 수는 각각 -3이나 -5를 해주어도 각각 3이나 5로 나누어 떨어집니다. 즉, 현재 인덱스 값(i)에 -3 또는 -5 해준 메모라이즈 값에 1을 더해준 값 중 가장 작은 값이 현재 인덱스에 대한 3이나 5로 나누어 떨어지는 가장 작은 수 즉, 우리가 구하고자 하는 결과값입니다.

 

앞서 언급했던대로 메모라이즈 배열을 2000으로 초기화해주었으므로 나누어 떨어지지 않는 수들이 자동으로 필터가 되며 n이 나누어 떨어지지 않더라도 2000과 2000을 비교한 꼴이 되므로 최종적으로 2000이 결과값이 되며 이러한 경우 -1을 출력시키도록 하면 됩니다.

 

 

참고자료

• https://www.acmicpc.net/problem/2839
• https://jhhj424.tistory.com/40