N과 M문제집
1부터 12까지 시리즈가 있는 N과 M 문제집
순열, 조합을 연습하는 N과 M 시리즈 문제다. 백준님께서 1~4번 문제가 매우 중요하다고 하셨다.
문제
N과M(1) 백준 15649번
리뷰
재귀 호출을 이용해서 N개중에 M개를 고른다.
M개를 고를 때, permu() 함수는 매개변수로 지금 '몇 번째' 숫자를 고른다는 기준을 잡는다.
int check[ ] 배열을 이용해 특정 숫자를 골랐는지/안골랐는지 표시한다.
숫자 중복을 허용하지 않기 때문에 선택 여부 표시를 위해 필요하다.
코드
#include <iostream>
using namespace std;
int N, M;
int check[10]; // 확인 여부
int answer[10]; // 선택한 인덱스
void permu(int idx){ // 'idx' 번째에 어떤 수를 놓을지 고른다.
if(idx > M){ // 이미 M개를 골랐으니까, M번째를 초과하는 순간 종료.
// 수열 출력
for(int p = 1; p <= M; p++){
cout << answer[p] << ' ';
}
cout << '\n';
return;
}
for(int i = 1; i <= N; i++){
if(check[i]) continue; // 이미 선택된 수는 지나간다
check[i] = 1; // 선택 함
answer[idx] = i; // idx 자리에 숫자 i 배치
permu(idx+1); // 다음 자리의 숫자 고르러 재귀
check[i] = 0; // 선택 안함
}
}
int main(void){
freopen("input.txt", "rt", stdin);
cin >> N >> M;
permu(1);
return 0;
}
문제
N과M(2) 백준 15650번
백준님이 강조하셨다 중요하다고.
리뷰
오름차순 수열을 출력하되, 숫자가 중복되지 않도록 한다.
즉, 이미 고른 숫자보다 큰 숫자부터 골라야 한다.
코드 1
#include <iostream>
#include <algorithm>
using namespace std;
// N과 M (2)
int N, M;
bool check[10];
int answer[10];
void go(int index, int start){
if(index == M){
// 수열 출력
for(int i = 0; i < M; i++){
cout << answer[i] << ' ';
}
cout << '\n';
return;
}
for(int i = start; i <= N; i++){
if(check[i]) continue; // 이미 선택된 숫자라면 지나간다.
check[i] = true;
answer[index] = i; // index 자리에 i를 선택한다.
go(index+1, i+1); // index+1 자리에 (==다음 자리)숫자를 고르기 위해 재귀 호출.
check[i] = false;
}
}
int main(void){
scanf("%d %d", &N, &M);
go(0, 1); // 0번째를 채우자.
return 0;
}
코드2
선택 한다/ 안한다의 관점
함수 시그니처는 아래와 같다.
void go(int num, int selected_cnt);
// num 에는 1부터 n까지의 숫자가 들어온다. 1, 2, 3, ... n
// selected_cnt는 0부터 m-1까지 숫자가 들어온다.
1부터 n까지 수가 들어오는데, 이 숫자를 선택 할지, 말지를 선택한다.
selected_cnt 가 m이 되는 순간 수열을 출력한다.
선택 한다면, selected_cnt 자리에 num을 넣는다.
arr[selected_cnt] = num; // 선택함
go(num+1, selected_cnt+1);
arr[selected_cnt] = 0; // 선택 안함
go(num+1, selected_cnt);
#include <iostream>
using namespace std;
// n과 m (2)
int n, m;
int arr[10]; // num 숫자를 선택 한다/안한다를 표시
// num 에는 1부터 n까지의 숫자가 들어온다.
// selected_cnt는 0부터 m-1까지 숫자가 들어온다.
void go(int num, int selected_cnt){ // num 숫자를 선택 한다/안한다 , 선택한 수의 개수
if(selected_cnt == m){
// 수열 출력
for(int i = 0; i < m; i++){
printf("%d ", arr[i]);
}
cout << '\n';
return;
}
if(num > n) return; // n을 초과하면 리턴
arr[selected_cnt] = num; // 선택함
go(num+1, selected_cnt+1);
arr[selected_cnt] = 0; // 선택 안함
go(num+1, selected_cnt);
}
int main(void){
scanf("%d %d", &n, &m);
go(1, 0);
return 0;
}