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

문제접근🤔

• 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);
}