문제 번호 : 15649번
난이도 : Sliver 3
시간 제한메모리
| 1 초 | 512 MB |
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
예제 입력 1
3 1
예제 출력 1
1
2
3
예제 입력 2
4 2
예제 출력 2
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3
풀이)
이 문제는 숫자가 1부터 N 만큼의 숫자중 M까지의 길이를 출력하는 문제이다. 그리고 중복되는 숫자를 넣어서는 안된다.
그러면 중복되지 않는 숫자 중 모든 해를 찾아서 출력해주면 된다.
본인은 백트래킹 알고리즘을 사용하여 풀어보곘다.
먼저 백트래킹이란 해를 찾는 도중 해가 절대 될 수 없다고 판단되면, 되돌아가서 해를 다시 찾아가 해를 찾는 알고리즘이다.
백트래킹의 기본은 재귀를 통해서 다음 함수에서 답을 찾는 것이 핵심이다.
이번 문제에서는 숫자를 M 만큼 출력 하는 것이기 때문에
다음 해를 찾으면서 넘어가는 count가 M이랑 같아 졌을 때 그동안 찾은 숫자들을 출력해주면 된다.
그리고 count 와 M이랑 다를 때는 1부터 N만큼의 숫자를 반복문을 돌면서 현재 번호를 내가 사용하였는지 체크하고, 사용하지 않았다면 해당 숫자를 사용한다. 그리고 나서 count가 M과 같아지면 스택 프레임을 없애면서 다음 숫자가 들어올 자리를 만들어줄 것이다.
코드)
#include <bits/stdc++.h>
using namespace std;
vector<int> vec;
int N, M;
int check[9];
void func(int n){
if(n == M){
for(int i=0; i<vec.size(); i++){
cout << vec[i] << " ";
}
cout << "\n";
return;
}
for(int i=1; i<=N; i++){
if(!check[i]){
check[i] = true;
vec.push_back(i);
func(n+1);
check[i] = false;
vec.pop_back();
}
}
}
int main() {
cin >> N >> M;
func(0);
return 0;
}
그렇다면 예제 2번을 예로 들면 2까지의 count를 찾아서 출력하고나면
1, 2가 되있던 형태에서 2를 제거하고 1만남게된다. 그리고 해당 스택 프레임에서 다시 반복문을 돌면서 다음 사용하지 않았던 3을 찾아서 1,3을 만들고, 다시 출력하는 형태가 될 것이다.
이렇게 모든 경우의 수를 만들어서 출력하는 형태가 된다.