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

문제링크 : https://www.acmicpc.net/problem/17212

17212번: 달나라 토끼를 위한 구매대금 지불 도우미

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, dp[100001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    dp[1]=1; dp[2]=1;
    dp[3]=2; dp[4]=2;
    dp[5]=1; dp[6]=2; dp[7]=1; //초기값 종류 7원까지 있기 떄문에 7까지

    for(int i=8; i<=N; i++)
    {
        dp[i] = min({dp[i-1], dp[i-2], dp[i-5], dp[i-7]}) + 1; //각각의 동전 종류를 뺐을 떄 최솟값 비교
    }

    cout << dp[N];

    return 0;
}

 

먼저 종류가 7원까지 있기 때문에 7원까지 dp의 초기값을 설정하였다.

 

이후 8부터 N까지는 문제에 주어진 동전의 종류인 1원, 2원, 5원 7원에 대해 각각의 동전을 사용했을 때의 최소값을 비교한후에 1을 더한 값으로 갱신해준다.