https://www.acmicpc.net/problem/15650
문제
> 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성해라.
1. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
2. 고른 수열은 오름차순이어야 한다.
> 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다.
중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.접근
백트래킹을 사용해 재귀로 수열을 조합하여 조건을 만족하면 출력하고, 아니면 다시 탐색한다.
문제해결
> 백트래킹으로 쓸 재귀함수인 numbers함수를 정의해준다.
재귀를 깰 조건으로 수열(result)의 크기가 입력받은 M일 때 수열을 출력하고 재귀를 깬다.
> 조건에 성립하지 않으면 수열을 채워야한다. 함수의 매개밴수로 받은 x값을 초기값으로 자릿수를 채운다. 처음은 1을 입력받기 때문에 첫 재귀는 i는 1부터 시작한다.
> 1일 때 아직 1을 쓴적이 없으므로 조건문이 동작한다. 수열의 첫값으로 1을 넣고, 1을 마킹한다음 다음 자리를 위해 해당 함수를 재귀한다.
> 인수로 이미 나왔던 수열, 반복되는 조합을 피하기 위해 i+1을 받아 넣는다. 그럼 예를 들어 1,2를 출력한적이 있다면 2일 때 i+1이므로 2보다 작은값, 같은값이 탐색되지않아 2,1 2,2가 나오지않는다.
> 위 과정을 통해 수열을 채우면 numbers에 i+1이므로 N+1값이 들어갈 때가 있다. N+1값이 들어가면 반복문에서 i = N+1부터 N과 같거나작을 때까지의 조건에 false가 되어 반복문이 돌아가지않고 해당 재귀가 끝난다. 그래서 바로 탐색을 종료한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> result;
vector<bool> visited;
void numbers(int x)
{
if (result.size() == M) //넣었더니 크기가 M에 만족하면
{
for (auto a : result)
cout << a << " ";
cout << '\n'; //벡터에 들어있는 수열 출력해
return;
}
for (int i = x; i <= N; i++) //크기가 M을 만족 못하면
{
if (!visited[i]) //아직 안썼던 숫자라면
{
result.push_back(i); //결과값에 추가
visited[i] = true; //썼다고 마킹
numbers(i+1); //재귀(다음 자릿수 채우기 or M만족시 출력및 재귀 깨기)
result.pop_back(); //바로 위 재귀 꺠면(자릿수 만족) result 맨뒤 제거
visited[i] = false; //방금 썼던 i 다시 안썻다고 표시, 직전 재귀의 i값으로 쓰기위해
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
visited.assign(N+1, false);
numbers(1);
}
후기
visited 값을 false로 바꾸지 않고 했을 때 앞서 1,2,3이 나왔다면 뒤에 2,3에대해 true로 되어 해당 값으로 시작하는, 해당 수를 갖는 수열이 나오지않았다.
문제를 보면 결국 모든 수열은 앞 자리수보다 큰 수만 나오기 때문에 다음 재귀에 현 재귀보다 큰수를 넣어 돌려주면된다.
생각하기까지 어렵지만 의외로 단순한 해결책이었다.
