링크
https://www.acmicpc.net/problem/15650
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
고른 수열은 오름차순이어야 한다.
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이
👨🏻💻 백트래킹 풀이
// 백트래킹 combination(조합)..arr랑 isused 배열이 필요.
// 조합일땐 반복문 시작점 st를 따로 설정해줘야한다.
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;
int n, m;
int arr[10];
bool isused[10];
void solve(int cur) { //cur은 현재 arr에 넣은 갯수
//base condition 다 넣어서 cur이 m이 됐을때 출력하고 리턴
if (cur == m) {
for (int i = 0; i < m; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
return;
}
int st = 1; //시작지점, k = 0일 때에는 st = 1
if (cur != 0)
st = arr[cur - 1] + 1; // k != 0일떄는 st = arr[cur-1]+1 -> 재귀 들어가기 바로 전에 넣은 원소 + 1 부터 시작.
for (int i = st; i <= n; i++) {
//넣을때 true , 끝나고 false
if (isused[i] == false) {
arr[cur] = i; //현재 넣은 갯수인 cur을 인덱스로 사용하고 i를 삽입
isused[i] = true;
solve(cur + 1);
isused[i] = false;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
// 백트래킹 combination 구현..array랑 bool타입 배열이 필요.
cin >> n >> m;
solve(0);
}👨🏻💻 next_permutation 이용한 풀이
//고른 수열이 오름차순이어야 하니까 결국은 combination을 구하는거다.
#include <iostream>
#include <vector>
#include <numeric>
#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), k(n);
iota(v.begin(), v.end(), 1);
fill(k.begin() + m, k.end(), 1); // 0 0 0 1이 되야 next_permu로 오름차순으로 출력한다.
do {
vector <int> tmp;
for (int i = 0; i < n; i++)
if (k[i] == 0)
tmp.push_back(v[i]);
for (auto i : tmp) cout << i << ' ';
cout << '\n';
} while (next_permutation(k.begin(), k.end()));
}설명
고른 수열이 오름차순이어야 하니까 결국은 combination을 구하는거다.
👨🏻💻 백트래킹 풀이
백트래킹 combination(조합).. arr랑 isused 배열이 필요하다.
조합일땐 반복문 시작점 st를 따로 설정해줘야한다.
st = arr[cur-1]+1 : 재귀 들어가기 바로 전에 넣은 원소 + 1 부터 반복문 시작한다. 조합은 반복이 안되기때문에 재귀함수 호출 전에 arr에 들어간 원소는 사용중인 원소이기 때문이다. 그리고 그 원소보다 작은 원소는 이미 모든 경우의 수를 탐색한 원소다. 따라서 다시는 나오면 안되기 때문이다.
👨🏻💻 next_permutation 이용한 풀이
fill(k.begin() + m, k.end(), 1); // 0 0 0 1이 되야 next_permu로 오름차순으로 출력한다.
k 벡터를 채울때 next_permutation을 사용할려면 순차적으로 먼저 0은 m의 개수만큼 채우고 나머지는 1로 채워야한다. next는 다음 순열을 찾아내기 때문에 가장 작은 수여야 한다.
