문제접근
•
dp에는 해당 돈을 만드는데에 필요한 최소 동전 개수를 담는다
•
dp[7]까지는 미리 초기화를 해둔다
•
dp[i]에서는 dp[i]까지 동전 1개를 남겨둔 녀석들의 경우의 수 중 가장 최소인 녀석을 확인한다
◦
dp[i - 1] : 1원짜리 동전 1개만 추가되는 상황
◦
dp[i - 2] : 2원짜리 동전 1개만 추가되는 상황
◦
dp[i - 5] : 5원짜리 동전 1개만 추가되는 상황
◦
dp[i - 7] : 7원짜리 동전 1개만 추가되는 상황
dp가 그 금액까지의 최소 동전 개수를 보장하기 때문에 거기서 1개만 추가되어도 최소가 보장된다
놓쳤던 부분
코드
2288 KB
0 ms
#include <iostream>
#include <algorithm>
using namespace std;
int main(void) {
int dp[100001] = {0, };
int n;
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.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;
for (int i = 8; i <= n; i++)
dp[i] = min(min(dp[i - 1], min(dp[i - 2], dp[i - 5])), dp[i - 7]) + 1;
cout << dp[n];
return (0);
}
C++
복사