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

문제

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

 

문제 이해

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력한다.
• 고른 수열은 오름차순이어야 한다.

 

문제 풀이

💡 DFS를 이용한 백트래킹

이전에 올린 N과 M (1) 문제에서, 출력할 수열이 오름차순인 것만 추가되었다.

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

N과 M (1)과 풀이 방식이 비슷한데, for 반복문에서 i값을 이용하면 중복없이 오름차순으로 수를 고를 수 있다.

그래서 방문 표기 배열이 필요하지 않다.

 

1. 종료 조건
   : M개의 수를 모두 선택했을 때
2. 탐색
   - 지정된 수부터 N까지 탐색을 반복한다. 지정된 수는 1부터 N까지 증가하여, 수열이 오름차순이 되도록 한다.
   - 탐색한 수를 출력할 배열에 삽입한다.
   - 탐색이 끝난 수를 배열에서 제거한다.
3. 탐색 종료
   - 선택한 M개의 수가 담긴 배열을 출력 후 탐색을 종료한다.

 

코드

#include<iostream>
#include<vector>

using namespace std;

int N, M;
vector<int> v;

void dfs(int num, int cnt) {
    if (cnt == M) {
        for (int i: v)
            cout << i << ' ';
        cout << '\n';
        return;
    }

    for (int i = num; i <= N; i++) {
        v.push_back(i);
        dfs(i + 1, cnt + 1);
        v.pop_back();
    }
}

int main() {
    cin >> N >> M;

    dfs(1, 0);

    return 0;
}