링크
https://www.acmicpc.net/problem/15655
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.
N개의 자연수 중에서 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이
👨🏻💻 백트래킹 풀이(처음에 푼 풀이)
//백트래킹.. 고른 순열이 오름차순이면 조합 nCr, arr배열 isused 배열 필요.
//조합이면 재귀 반복문의 시작점(st)을 설정해야한다.
// N개의 자연수를 입력 받을 num배열 필요.
// isused의 인덱스가 num의 원소를 의미할 수 없으므로
//isused[i]가 num[i]의 사용여부를 나타내게끔 설정.
// st를 설정할때 arr에 넣은 값을 인덱스(st)로 사용할 수 없기 때문에
//따로 for문을 돌려서 현재 재귀함수 호출 직전에 arr에 넣은 값 arr[cur - 1]보다
// 큰 num 원소를 찾고 그때의 인덱스를 st로 설정한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[10];
int num[10];
bool isused[10];
int st;// st = 0 초기화 설정.
void setSt( int cur ) {
for (int i = 0; i < n; i++) {
if (num[i] > arr[cur - 1]) { //arr에 직전에 넣은 값보다 크다면 거기서부터 시작하면돼
st = i;
return;
}
}
}
void solve(int cur) { //현재 cur개까지 수를 택했음.
if (cur == m) { // m개를 모두 택했으면
for (int i = 0; i < m; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
}
// 'cur==0일때' 'int st = 1;' 조건은 순차적인 원소들에서 arr에 i가 들어갈때
// 1부터 들어가야되기 때문에 사용한거다.
//지금은 인덱스가 0일때의 isused[0], num[0]을 쓰기 때문에 처음에 st=0 초기화 설정이면 충분.
if (cur != 0){
setSt(cur);
}
for (int i = st; i < n; i++) {
if (isused[i] == false) {
arr[cur] = num[i];
isused[i] = true;
solve(cur + 1);
isused[i] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num, num + n); //정렬
solve(0);
}👨🏻💻 백트래킹 풀이(바킹독 문제집 제공 풀이)
//백트래킹.. 고른 순열이 오름차순이면 조합 nCr, arr배열 isused 배열 필요.
//조합이면 재귀 반복문의 시작점(st)을 설정해야한다.
// N개의 자연수를 입력 받을 num배열 필요.
// isused의 인덱스가 num의 원소를 의미할 수 없으므로
//isused[i]가 num[i]의 사용여부를 나타내게끔 설정.
// st를 설정할때 arr에 넣은 값을 인덱스(st)로 사용할 수 없기 때문에
// 애초에 arr에 num원소를 삽입하는게 아니라 num[]에 대응하는 인덱스를 기록해두고
// 나중에 출력할 때 인덱스에 대응되는 num원소를 출력한다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
int arr[10];
int num[10];
bool isused[10];
void solve(int cur) { //현재 cur개까지 수를 택했음.
if (cur == m) { // m개를 모두 택했으면 출력하고 리턴
for (int i = 0; i < m; i++) {
cout << num[arr[i]] << ' '; //arr에 기록해둔 인덱스에 대응되는 수를 출력.
}
cout << '\n';
return;
}
// 'cur==0일때' 'int st = 1;' 조건은 순차적인 원소들에서 arr에 i가 들어갈때
// 1부터 들어가야되기 때문에 사용한거다.
//이 문제는 인덱스가 0일때의 isused[0], num[0]을 쓰기 때문에 처음에 int st=0;.
int st = 0; // cur==0일때
if (cur != 0){
st = arr[cur - 1] + 1;// 현재 재귀함수 호출 직전에 arr에 넣은 값(인덱스)보다 +1해서
//반복문 시작한다.
}
for (int i = st; i < n; i++) {
if (isused[i] == false) {
arr[cur] = i; //arr에 num원소를 넣는게 아니라 해당 인덱스를 넣는다
isused[i] = true;
solve(cur + 1);
isused[i] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> num[i];
}
sort(num, num + n); //정렬
solve(0);
}👨🏻💻 next_permutation 이용한 풀이
//고른 수열이 오름차순 이므로 조합.
//중복이 없으므로 next_permutation 가능
//조합 -> N개의 원소를 입력받을 백터 v, 0과 1을 저장할 백터 t 필요
#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<int> v(n), t(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
fill(t.begin()+ m, t.end(), 1); // m개만큼 0 그리고 그 다음 인덱스부터 나머지 1.
sort(v.begin(), v.end()); //정렬
do {
for (int i = 0; i < n; i++) {
if (t[i] == 0) {
cout << v[i] << ' ';
}
}
cout << '\n';
} while (next_permutation(t.begin(), t.end()));
}설명
👨🏻🏫 백트래킹 풀이
백트래킹.. 고른 순열이 오름차순이면 조합 nCr, 중복 없음, arr배열 isused 배열 필요.
조합이면 재귀 반복문의 시작점(st)을 설정해야한다.
N개의 자연수를 입력 받을 num배열 필요.
isused의 인덱스가 num의 원소를 의미할 수 없으므로
isused[i]가 num[i]의 사용여부를 나타내게끔 설정.
🔥 st 설정 방법에서 문제가 생겼다.
🤷🏻♂️ 처음에는 푼 풀이에선
st를 설정할때 arr에 넣은 값을 인덱스(st)로 사용할 수 없기 때문에
따로 for문을 돌려서 현재 재귀함수 호출 직전에 arr에 넣은 값 arr[cur - 1]보다
큰 num 원소를 찾고 그때의 인덱스를 st로 설정한다.
🙆🏻♂️ 정답 풀이의 방법이 훨씬 깔끔하다.
⭐⭐⭐ st를 설정할때 arr에 넣은 값을 인덱스(st)로 사용할 수 없기 때문에
애초에 arr에 num원소를 삽입하는게 아니라 num[]에 대응하는 인덱스를 기록해두고
나중에 출력할 때 인덱스에 대응되는 num원소를 출력한다.
👨🏻💻 next_permutation 이용한 풀이
고른 수열이 오름차순이므로 조합 nCr (뽑은 순열 간의 중복이 없다).
원소 간의 중복이 없으므로 next_permutation 가능
조합 -> N개의 원소를 입력받을 백터 v, 0과 1을 저장할 백터 t 필요.
