문제
리뷰
1부터 N까지의 자연수가 아니라, 입력받은 N개의 수열을 이용한다.
중복을 허용하지 않고 2개 고르는 것이라서 중복체크를 위해 ch [10] 배열이 필요하다.
수열은 사전 순으로 증가하는 순으로 출력해야 하니까, 입력받자마자 sort() 했다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
// n과 m (5)
int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.
int arr[10]; // 입력받은 수열 저장.
int ch[10]; // 중복을 허용하지 않으니까, 체크 배열이 필요하다.
int answer[10];
void go(int index){
if(index == M){
for(int i = 0; i < M; i++){
printf("%d ", answer[i]);
}
cout << '\n';
return;
}
for(int i = 0; i < N; i++){
if(ch[i]) continue;
ch[i] = 1;
answer[index] = arr[i];
go(index+1);
ch[i] = 0;
}
}
int main(void){
cin >> N >> M;
for(int i = 0; i < N; i++){
scanf("%d", &arr[i]);
}
sort(arr, arr+N);
go(0);
return 0;
}문제
리뷰
수열의 중복을 허용하지 않고, 사전 순으로 증가하는 순서로 출력해야 한다.
수열은 오름차순이어야 하므로 go 함수에 start 변수를 넣어서 이전 인덱스 보다 큰 인덱스부터 수열의 숫자를 고르도록 했다.
코드
#include <iostream>
#include <algorithm>
using namespace std;
// n과 m (6)
// 중복 허용 안 함. 오름차순 수열.
int N, M; // 1부터 N까지의 자연수 중에서 M개를 고른 수열.
int arr[10];
int ch[10];
int answer[10];
void go(int index, int start){
if(index == M){
for(int i = 0; i < M; i++){
printf("%d ", answer[i]);
}
cout << '\n';
return;
}
for(int i = start; i < N; i++){
if(ch[i]) continue;
ch[i] = 1;
answer[index] = arr[i];
go(index+1, i+1);
ch[i] = 0;
}
}
int main(void){
cin >> N >> M;
for(int i = 0; i < N; i++){
scanf("%d", &arr[i]);
}
sort(arr, arr+N);
go(0, 0);
return 0;
}728x90
'알고리즘 > 백준' 카테고리의 다른 글
| 주사위 세개 c++ 백준 2480 (0) | 2021.11.19 |
|---|---|
| BFS 스페셜 저지 백준 16940 c++ (0) | 2020.11.05 |
| 알고스팟 1261번 백준 c++ (0) | 2020.10.22 |
| 부등호 백준 2529번 c++ (0) | 2020.10.21 |
| 부분수열의 합 백준 1182번 (0) | 2020.10.20 |