16922번: 로마 숫자 만들기
2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다.
www.acmicpc.net
1, 5, 10, 50을 배열에 넣어놓고 조합으로 해결하였습니다.
인덱스와 갯수와 합을 유지시키면서 재귀를 돌려줍니다.
N개를 뽑으면 숫자를 저장하였는데 이 때 중복된 값을 넣으면 안되므로 set에 넣어줍니다.
함수가 끝나고 최종 set의 크기를 출력하시면 됩니다.
|
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
|
#include <iostream>
#include <set>
using namespace std;
set<int> s;
int list[4];
int N;
void init() {
list[0] = 1;
list[1] = 5;
list[2] = 10;
list[3] = 50;
}
void func(int idx, int cnt, int sum) {
if (cnt == N) {
if (sum > 0) s.insert(sum);
return;
}
for (int i = idx; i < 4; i++) {
func(i, cnt + 1, sum + list[i]);
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
cin >> N;
init();
func(0, 0, 0);
cout << s.size() << '\n';
return 0;
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 2023 신기한 소수 (0) | 2021.03.16 |
|---|---|
| boj 14500 테트로미노 (0) | 2021.03.15 |
| boj 1987 알파벳 (0) | 2021.02.18 |
| boj 3109 빵집 (0) | 2021.02.18 |
| boj 17406 배열 돌리기 4 (0) | 2021.02.10 |