[백준 33941] 잔돈 싫어 [Java]

문제

http://boj.ma/33941

33941번: 잔돈 싫어

 

---

풀이

문제 요약

조건을 만족하는 환불 가능한 교통 카드의 금액의 최대 합이 500으로 나누어 떨어지도록 적절하게 선택해야 한다.

아이디어

500으로 나누어 떨어지는 최대 합을 구해야 하므로, 환불 가능한 교통 카드의 금액을 500으로 나눈 나머지와, 환불 비용 500원을 제외한 금액에 대한 배낭문제로 볼 수 있다.

점화식은 다음과 같다.

dp[n][i]: n번째 환불 가능한 카드들의 잔액 합을 500으로 나눈 나머지가 i가 되는 환불 금액의 최대 합

n - 1번째 상태 까지만 필요하므로 다음과 같이 축약할 수 있다.

dp[i]: 환불 가능한 카드들의 잔액 합을 500으로 나눈 나머지가 i가 되는 환불 금액의 최대 합

        long[] dp = new long[500];
        Arrays.fill(dp, -1);
        dp[0] = 0;

        for (int a : A) {
            int curR = a % 500;
            long realA = a - 500;

            long[] temp = dp.clone();
            for (int prevR = 0; prevR < 500; ++prevR) {
                final int nr = (prevR + curR) % 500;
                if (dp[prevR] == -1) {
                    continue;
                }
                temp[nr] = Math.max(temp[nr], dp[prevR] + realA);
            }
            dp = temp;
        }

풀이 시간

30분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/33941.java

problem-solving/baekjoon-online-judge/normal/33941.java at main · rogi-rogi/problem-solving