https://www.acmicpc.net/problem/15652
문제
> 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
> 1부터 N까지 자연수 중에서 M개를 고른 수열
> 같은 수를 여러 번 골라도 된다.
> 고른 수열은 비내림차순이어야 한다.
> 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.접근
재귀를 사용하여 각 자리수마다 가능한 수를 넣어 주고 수열의 길이가 입력으로 받은 M에 만족한다면 저장된 수열을 출력해주고 가능한 다음 수열을 탐색한다.
문제에서 비내림차순이라고 했기 때문에 오름차순이고, 중복이 가능하다고했으니 재귀로 다음 수를 넘길 때 i를 넘겨주면 같은수에 대한 수열도 탐색하기 때문에 111, 222같은 조합이 가능하다.
문제해결
> 재귀의 탈출조건이자 수열의 출력조건을 입력받은 수열의 길이 M이 되면 rst에 저장된 수열을 출력하도록한다.
> 재귀에선 각 자리별로 함수의 인자로 받은 start값으로 탐색을 시작하며 size는 현재 탐색중이 수열의 자릿수가 된다.
> 흐름을 따라가보면 처음에 1,0으로 main에서 들어간다.
> 함수에서 조건에 걸리지 않고 반복문으로 들어가 1부터 입력받은 N까지 반복문을 도는데
각 반복문마다 재귀로 들어간다.
> 두번째 자리도 start가 1이 들어왔으므로 1부터 반복문이 돌며 재귀로 1,2가 들어간다.
1,2에 대해 마지막 세번째 자리도 1로 되고 1,3이 넘어갔을 때 재귀의 조건에 걸려 1,1,1이 출력된다.
>이제 return으로 다시 세번째 자리 탐색으로 돌아가 반복문이 1은 봤으므로 i++에 의해 2로 올라가 2,3으로 재귀가 넘어간다.
> 조건에 걸려 1,1,2가 출력된다.
> 이 흐름으로 중복이 가능한 비내림차순 구조의 수열이 나온다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int N, M;
vector<int> rst;
void Num(int start, int size)
{
if (size == M)
{
for (auto a : rst)
{
cout << a << " ";
}
cout << '\n';
return;
}
for (int i = start; i <= N; i++)
{
rst[size] = i;
Num(i, size + 1);
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> N >> M;
rst.resize(M);
Num(1, 0);
}
후기
문제가 거창해서 잘 읽어보니 비내림차순 -> 같은수로 이루어진 수열도 가능한 오름차순 이었다.
