[BOJ/백준 15650][C++] N과 M (2)

문제

https://www.acmicpc.net/problem/15650

백준 15650

 

문제 내용

1~N까지의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다.

이때 수열은 오름차순이어야 하며, 사전 순으로 증가하는 순서대로 출력해야 한다.

 

문제 풀이

N과 M (1)과 다르게 N과 M (2)는 수열이 오름차순이어야 한다는 조건이 추가되었다.

N과 M (1)은 몇 개를 선택했는지만 인자로 넘겨서 종료조건을 체크하면 되었지만, N과 M (2)는 오름차순 수열을 만들어야 하기 때문에, 이전에 어떤 값을 선택했었는지에 대한 정보도 넘겨주어야 한다.

또한, 오름차순을 유지하기 위해 이전에 선택한 값을 받아, 그 이후 값부터 for문을 돌기 때문에 used 배열도 필요 없다.

[BOJ/백준 15649][C++] N과 M (1)

 

코드

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> result(8, 0);

void back(int cnt, int before) {
    if (cnt == m) {
        // 여기서 출력 후 return
        for (int i = 0; i < cnt; i++) {
            cout << result[i] << ' ';
        }
        cout << "\n";
        return;
    }

    for (int i = before + 1; i <= n; i++) {
        result[cnt] = i;
        back(cnt + 1, i);
    }
}

int main() {
    cin >> n >> m;

    back(0, 0);
}