15663번: N과 M (9)
사용 언어: C++
문제
N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- N개의 자연수 중에서 M개를 고른 수열
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
풀이 1
하나의 수열을 일단 만들면 tmp는 가장 마지막에 만든 수열의 마지막 항을 저장하는데 수열을 만든 후 다음 수열의 마지막 항과 비교해서 같으면 중복으로 판단해 출력되지 않는다. 예를 들어 숫자들이 n=4 m=2, 1 2 2 9면 수열 1 2 를 만들면서 tmp = 2가 저장되고 그 이후에 다른 수열을 만들 것이다. 다른 수열이 만들어지면서 tmp=2와 num[i]에 저장된 중복된 2와 비교하면서 tmp != num[i]에 대입해보면 2 != 2여서 중복된 수열이 만들어지지 않는다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int num[10];
bool isused[10];
void func(int cur){
if(cur == m){
for(int i=0; i<m; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
int tmp=0;
for(int i=0; i<n; i++){
if(!isused[i] && tmp != num[i]){//중복 없게 이전 수열과 현 수열 비교
isused[i] = 1;
tmp = arr[cur] = num[i];
func(cur+1);
isused[i] = 0;
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++) cin >> num[i];
sort(num, num+n);
func(0);
return 0;
}
풀이 2
좀 더 직관적인 풀이로 num[i]의 값에 해당하는 index를 가진 bool check을 만들어서 이미 썼으면 check[num[i]]로 넘기는 풀이다.
#include <bits/stdc++.h>
using namespace std;
int n, m;
int arr[10];
int num[10];
bool isused[10];
void func(int cur){
if(cur == m){
for(int i=0; i<m; i++)
cout << arr[i] << ' ';
cout << '\n';
return;
}
bool check[10000] = {0,};
for(int i=0; i<n; i++){
if(!isused[i] && !check[num[i]]){
check[num[i]] = 1;
isused[i] = 1;
arr[cur] = num[i];
func(cur+1);
isused[i] = 0;
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for(int i=0; i<n; i++) cin >> num[i];
sort(num, num+n);
func(0);
return 0;
}
'BOJ > 백트래킹' 카테고리의 다른 글
15665번: N과 M (11) (BOJ C/C++) (0) | 2022.09.03 |
---|---|
15664번: N과 M (10) (BOJ C/C++) (0) | 2022.09.03 |
15657번: N과 M (8) (BOJ C/C++) (0) | 2022.09.02 |
15656번: N과 M (7) (BOJ C/C++) (0) | 2022.09.02 |
15655번: N과 M (6) (BOJ C/C++) (0) | 2022.09.02 |