[백준] 알고리즘 17212번 - 달나라 토끼를 위한 구매대금 지불 도우미 문제

문제

www.acmicpc.net/problem/17212

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

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[100001];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	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++) {
		if (i % 7 == 0) dp[i] = i / 7;
		else dp[i] = min({ dp[i - 7],dp[i - 5],dp[i - 2],dp[i - 1] }) + 1;
	}
	cout << dp[n];
}

풀이

1~7까지는 직접 몇개가 들어가는지 메모리에 적립시켜준다.

이후 8부터는 거스름돈을 낼 수 있는 경우들을 각각 비교해줘야 한다.

dp[i] = min({ dp[i - 7],dp[i - 5],dp[i - 2],dp[i - 1] }) + 1;

마지막에 +1은 dp[1] dp[2] dp[5] dp[7]인 자기자신을 더해줘야 한다,

이것때문에 좀 고민했는데 생각해보니 간단한거였으