https://www.acmicpc.net/problem/15665
방법 1: 중복 제거 한 숫자열로 조합
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 7;
int numbers[MAX];
int output[MAX];
void dfs(int N, int M, int depth)
{
if (depth == M)
{
for (int i = 0; i < M; ++i)
{
cout << output[i] << ' ';
}
cout << '\n';
return;
}
// 중복 허용. 정렬X
for (int i = 0; i < N; ++i)
{
output[depth] = numbers[i];
dfs(N, M, depth + 1);
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int tmp[MAX];
for (int i = 0; i < N; ++i)
{
cin >> tmp[i];
}
// 사전순 출력을 위해 오름차순 정렬
sort(tmp, tmp + N);
// 중복을 제거하여 숫자열 저장.
numbers[0] = tmp[0];
int idx = 1;
for (int i = 1; i < N; ++i)
{
if (tmp[i - 1] != tmp[i])
{
numbers[idx] = tmp[i];
++idx;
}
}
dfs(idx, M, 0);
return 0;
}
방법 2: map 사용
#include <iostream>
#include <algorithm>
using namespace std;
const int MAX = 8;
int numbers[MAX];
int output[MAX];
int cnt[MAX];
void dfs(int N, int M, int depth)
{
if (depth == M)
{
for (int i = 0; i < M; ++i)
{
cout << output[i] << ' ';
}
cout << '\n';
return;
}
/*
오름차순, 중복 허용X
한번 숫자를 쓸 때마다 개수 - 1
아직 숫자를 꺼내 쓸 수 있으면 선택 가능.
*/
for (int i = 0; i < N; ++i)
{
if (cnt[i] > 0)
{
--cnt[i];
output[depth] = numbers[i];
dfs(N, M, depth + 1);
++cnt[i];
}
}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M;
cin >> N >> M;
int tmp[MAX];
for (int i = 0; i < N; ++i)
{
cin >> tmp[i];
}
// 오름차순 정렬
sort(tmp, tmp + N);
// 각 숫자의 개수를 저장한 cnt배열 만들기
// numbers배열에 중복 제거한 숫자들 저장하기
int num = -1;
int idx = 0;
for (int i = 0; i < N; ++i)
{
if (num != tmp[i])
{
num = tmp[i];
numbers[idx] = tmp[i];
++cnt[idx];
++idx;
}
else
{
++cnt[idx - 1];
}
}
// 중복 제거한 숫자 개수 중에서 M개 뽑기
dfs(idx, M, 0);
return 0;
}
사실 N과 M (7) 문제와 비슷하다.
1 7 9 9 든, 1 1 1 7 7 7 9 9 든,
그냥 등장하는 숫자 1 7 9 <-- 이렇게 3개를 가지고 마구 조합하면 된다.
세부 구현에 대한 자세한 설명은
N과 M(9) 문제를 참고하면 된다.
'Algorithm > BOJ' 카테고리의 다른 글
[BOJ]10972번: 다음 순열(c++) (0) | 2020.05.10 |
---|---|
[BOJ]15666번: N과 M (12)(c++) (0) | 2020.05.10 |
[BOJ]15664번: N과 M (10)(c++) (0) | 2020.05.09 |
[BOJ]15663번: N과 M(9)(c++) (0) | 2020.05.09 |
[BOJ]15657번: N과 M (8) (c++) (0) | 2020.05.06 |
댓글