[BJO][C++] 14916 : 거스름돈

문제

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

 

코드

#include <iostream>

using namespace std;

int solution(int n){
    int ans = 0;

    // dp 초기 설정
    int dp[100001] = {0, -1, 1, -1, 2, 1};

    // n이 5보다 큰 경우, 직접 계산
    if(n > 5){
        for(int i = 6; i<=n; i++){

            // 현재 n보다 더 작은 값에 대한 결과값을 이용해 현재 내야 할 동전 개수 계산.
            /* 예를 들어 n = 9 라면 n=7 까지의 동전 개수는 계산이 완료된 상태이므로,
                n=7 의 동전(5원 1개, 2원 1개 -> 2개) 에
                남은 n=2(2원 1개)를 를 추가적으로 더해주면 됨. 
            */
            dp[i] = dp[i-2] + dp[i-(i-2)];

            // 만약 5원짜리 동전만을 이용해 계산하는 것이 적합한 경우
            if(i%5 ==0){
                int cal= i / 5;
                if(cal < dp[i]) dp[i] = cal;
            }

            // 만약 2원짜리 동전만을 이용해 계산하는 것이 적합한 경우
            if(i%2 ==0){
                int cal = i / 2;
                if(cal < dp[i]) dp[i] = cal;
            }
        }
    }

    ans = dp[n];
    return ans;
}

int main()
{
    int n;
    cin >> n;
    int ans = solution(n);
    cout << ans;

    return 0;
}

 

풀이

  원래 5원, 2원짜리 동전만으로 계산할 수 있는 경우에 대한 조건을 이용하지 않고 이중 for 문을 이용해 현재의 n부터 0까지 거꾸로 거슬러 올라가며 최적의 동전 개수를 찾아내는 방식을 이용했다. (중간에 break 걸어주기)

  그러나 시간 초과가 발생했다. 사실 입력 가능한 n이 크고, 또 이중 for 문을 이용할 때 시간 초과가 발생할 것이라고 예상을 하긴 했다.

  그래서 하나의 for 문을 이용해야겠다는 생각을 하게 되었고, 조건문을 걸어줌으로서 해결할 수 있었다.