Search
Duplicate
📗

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

주차
문제번호
17212
언어
C++
티어
실버
유형
DP
nj_Blog
nj_상태
이해도
100%
풀이
사람
이해도 2
13 more properties

문제접근

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++
복사