[백준]2839 - 설탕 배달 문제 풀이(Java,자바)

들어가며

이 문제는 솔직히 말하면 못 풀었다. 보통 30분 문제를 보고 못 풀면 바로 답지를 보는데 이상하게 어렵다 싶었더니 dp 였다..

dp를 더 열심히 공부해야겠다.. 화이팅 

반복문 방식과 dp 방식 모두 작성해보았다.

 

반복문 방식

코드

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int bagCount = 0;

        while (true) {
            // n이 5로 나누어 떨어지면 나눠서 종료
            if (n % 5 == 0) {
                bagCount += n / 5;
                break;
            }
            // 3kg 봉투 하나 사용
            n -= 3;
            bagCount++;

            // n이 음수가 되면 배달 불가
            if (n < 0) {
                bagCount = -1;
                break;
            }
        }

        System.out.println(bagCount);
    }

풀이법

가장 단순한 방식으로 반복문을 돌린다.

여기서 중요한 것은 5의 배수를 먼저 걸러야한다. 5가 가장 많아야 최소에 근접하기 때문이다.

그리고 5로 나누지 못한다면 3kg 하나를 선택한다.

그리고 음수가 됐는지 파악한다. 이때 음수가 됐다는 말은 5와 3으로 만들 수 없는 숫자임을 의미한다.

그렇게 최종 결과를 도출할 수 있다.

dp 방식

코드

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int dp[] = new int[5005];
        for (int i = 0; i < 5005; i++) {
            dp[i] = 5000;
        }
        dp[3] = 1;
        dp[5] = 1;

        for (int i = 6; i <= n; i++) {
            dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;
        }
        if (dp[n] >= 5000) {
            System.out.println(-1);
        } else {
            System.out.println(dp[n]);
        }
    }

풀이법

dp 라는 배열은 만든다. 이 인덱스는 n의 값으로 nkg라는 의미이다.

초기값을 모두 5000으로 준다. 이는 문제에서 n의 최대값이 5000이라 그렇게 설정했다.

이제 반복문을 돌린다.

이때, i-3과 i-5 중에 최소값을 찾는데, 이는 이전 상태라고 볼 수 있는 두 상태에서 최선의 경우를 찾는 것이다.

i-3이라는 건 3kg를 적게 가진 그 상태에서 최선의 개수를 의미한다. i-5도 마찬가지

그렇게 3과 5의 배수로만 구해지고 만들 수 없는 n 값은 자동으로 5000으로 처리되어 최종적으로 -1이 된다.