문제
상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?
예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.
n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 n이, 둘째 줄에 k가 주어진다. 셋째 줄부터 n개 줄에는 카드에 적혀있는 수가 주어진다.
출력
첫째 줄에 상근이가 만들 수 있는 정수의 개수를 출력한다.
|
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
|
#include<bits/stdc++.h>
using namespace std;
int card[10];
int n, k;
bool use[10];
set<int>ans;
void dfs(int cnt, int sum) {
if (cnt == k) {
ans.insert(sum);
return;
}
for (int i = 0; i < n; i++) {
if (!use[i]) {
use[i] = true;
if (card[i] < 10)
dfs(cnt + 1, sum * 10 + card[i]);
else
dfs(cnt + 1, sum * 100 + card[i]);
use[i] = false;
}
}
}
int main() {
cin >> n >> k;
for (int i = 0; i < n; i++)
cin >> card[i];
dfs(0, 0);
cout << ans.size() << '\n';
return 0;
}
|
cs |
dfs를 사용해서 모든 경우를 탐색했고 set을 이용해서 중복을 해결했다.
즉 set의 사이즈가 정답이 된다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 (BOJ) 2023 신기한 소수 (0) | 2020.11.13 |
|---|---|
| 백준 온라인 저지 (BOJ) 17499 수열과 시프트 쿼리 (0) | 2020.11.08 |
| 백준 온라인 저지 (BOJ) 10828 스택 (0) | 2020.11.08 |
| 백준 온라인 저지 (BOJ) 1417 국회의원 선거 (0) | 2020.11.06 |
| 백준 온라인 저지 (BOJ) 17266 어두운 굴다리 (0) | 2020.11.06 |