쌓고 쌓다
[백준] 거스름돈 14916번 C++ 풀이 본문
https://www.acmicpc.net/problem/14916
14916번: 거스름돈
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
www.acmicpc.net
#include <iostream>
#include <algorithm>
using namespace std;
int dp[100001];
int main(void)
{
int N;
cin >> N;
dp[1] = 999999;
dp[2] = 1;
dp[3] = 999999;
dp[4] = 2;
dp[5] = 1;
for (int i = 6; i <= N; i++) {
dp[i] = min(dp[i - 2] + 1, dp[i - 5] + 1);
}
if (dp[N] == 999999)
cout << "-1";
else
cout << dp[N];
}2원과 5원으로 금액을 맞춰야 하므로
i번째에서 각각 2와 5를 감소시킨 금액을 만드는 방법 중 더 작은 개수에 +1을 (2원과 5원을 추가해서 i 금액을 맞출 것이므로) 해주면 됩니다.
DP 풀이 방법이었습니다.
'알고리즘 > 백준' 카테고리의 다른 글
| [백준] RGB거리2 17404번 C++풀이 (0) | 2022.01.27 |
|---|---|
| [백준] 로봇 조종하기 2169번 C++ 풀이 (0) | 2022.01.25 |
| [백준] 양팔저울 2629번 C++ 풀이 (0) | 2022.01.22 |
| [백준] 연속합2 13398번 C++ 풀이 (0) | 2022.01.21 |
| [백준] 작업 2056번 C++ 풀이 (0) | 2022.01.20 |
Comments