[백준 알고리즘] 17212번: 달나라 토끼를 위한 구매대금 지불 도우미 (C++)

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

문제

문제 달나라 토끼들이 사용하는 화폐는 동전뿐이다. 동전의 종류는 1원, 2원, 5원, 7원 이렇게 4종류가 있다. 물건을 사고 동전으로 계산을 하는데 동전의 개수가 최소가 되도록 지불하지 않는 것은 불법이다. 예를 들어, 17원을 지불할 때 7원짜리 동전 1개와 5원짜리 동전 2개로 지불해야 합법이고, 7원짜리 동전 2개와 2원짜리 동전 1개, 1원짜리 동전 1개로 지불해도 17원이 되지만, 총 동전의 개수가 4개가 되어 최소 개수가 아니므로 불법이다.

지불 금액을 입력받아 합법이 되는 동전 개수를 출력으로 내어주는 프로그램을 작성해보자.

입력 첫 번째 줄에 달나라 토끼가 지불해야하는 금액 N(0 ≤ N ≤ 100,000)이 주어진다.

출력 첫 번째 줄에 달나라 토끼가 합법적으로 낼 수 있는 동전의 개수를 출력한다.

풀이

최소한의 동전을 사용하면서 문제를 해결해야하기 때문에, DP로 접근이 가능했다. 이 문제는 지난 겨울에 풀다가 포기한 문제인데, 이제 DP에 어느정도 감이 생기는 것 같다.

일단, 지불해야하는 값이 7로 딱 나누어 떨어지는 값이라면, 복잡하게 생각할 필요가 없을 것이다, 7원 짜리로 다 내면 되니까. 그럼 이제 다른 경우가 문제인데, 결국 문제를 최소화 하려면, 계속 두 그룹으로 나누어주는게 좋다는 생각이 들었다.

DP를 통해 우리가 알아야할 값 N 이전에 있는 모든 최적의 값을 가지고 있다고 가정하고, N 을 두 그룹으로 나눌 수 있는 가장 최적의 경우인 N-1, N-2, N-5, N-7 중 가장 작은 값을 구한다. 그리고 이 값과 1, 2, 5, 7원 중 해당 값을 만든 동전 하나를 내면 이전까지 최소 갯수 + 한개의 동전으로 N을 만들 수 있기 때문이다.

따라서 다음과 같은 세 경우를 코드로 구현하는 것으로 해결할 수 있었다.

1. N이 1, 2, 5, 7 일 경우, dp[N] = 1.
2. N이 7로 나누어 떨어지는 경우, dp[N] = N/7.
3. 위 두 가지 경우에 해당이 안되는 경우, dp[N] = min(dp[N-1], dp[N-2], dp[N-5], dp[N-7]) + 1.

코드

#include <cstdio>
#include <algorithm>

using namespace std;

int dp[100002];

int main()
{
    int N;
    scanf("%d", &N);

    dp[1] = 1;
    for (int i = 2; i <= N; i++)
    {
        if (i % 7 == 0)
            dp[i] = i / 7;
        if (i == 2 || i == 5 || i == 7)
            dp[i] = 1;
        else
        {
            dp[i] = min(dp[i - 1] + 1, dp[i - 2] + 1);
            if (i >= 5)
                dp[i] = min(dp[i], dp[i - 5] + 1);
            if (i >= 7)
                dp[i] = min(dp[i], dp[i - 7] + 1);
        }

    }
    printf("%d", dp[N]);
    return 0;
}