https://www.acmicpc.net/problem/1398
1, 10, 25, 100, 1000, 2500, 10000, 100000, 250000, 1000000 ...
위 동전들을 적절히 사용하여 N을 만들기 위한 최소 갯수를 구하는 문제입니다.
동전들을 3개씩 끊어본다면
(1, 10, 25)
(1, 10, 25) * 100
(1, 10, 25) * 100 * 100
(1, 10, 25) * 100 * 100 * 100
이런식으로 규칙이 된다는 것을 알 수 있습니다.
그러면 굳이 문제에서 요구하는 큰 범위까지 갈 필요 없이 100 단위로 끊어서 접근한다면 간단하게 해결할 수 있습니다.
같은 금액에서의 답은 똑같기 때문에 dp를 사용했습니다.
그리고 dp 배열을 초기화할 필요도 없습니다.
(1, 10, 25) 으로 99원을 만들든, (100, 1000, 2500) 으로 9900원을 만들든 똑같은 결과가 나오기 때문입니다.
여기까지 오셨다면 구현은 간단합니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <cstring>
#include <algorithm>
#define MAX 101
using namespace std;
typedef long long ll;
int dp[MAX];
int list[3] = { 1,10,25 };
ll N;
int solve(int n) {
if (!n) return 0;
int& ret = dp[n];
if (ret != -1) return ret;
ret = 1e9;
for (int i = 0; i < 3; i++) {
if (n < list[i]) continue;
ret = min(ret, solve(n - list[i]) + 1);
}
return ret;
}
void func() {
memset(dp, -1, sizeof(dp));
int ret = 0;
while (N) {
ret += solve(N % 100LL);
N /= 100LL;
}
cout << ret << '\n';
}
void input() {
cin >> N;
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
int tc;
cin >> tc;
while (tc--) {
input();
func();
}
return 0;
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 30461 낚시 (0) | 2024.07.28 |
|---|---|
| boj 17258 인기가 넘쳐흘러 (0) | 2024.07.20 |
| boj 1229 육각수 (0) | 2024.06.30 |
| boj 25378 조약돌 (0) | 2024.06.29 |
| boj 2216 문자열과 점수 (0) | 2024.06.28 |