백준 15650번, N과 M(2)

백준 15650번 c++ 문제풀이

문제:

백준 15650

풀이:

1. 깊이우선탐색으로 접근했다.
2. 재귀함수 dfs를 1부터 시작하고, 수열 중 몇번째(count)인지 다음 수열을 선택할 때 넘겨준다.
3. 선택된 수는 arr[count]에 저장해준다.
4. count가 m이랑 같다면 그 수열을 출력해준다.
5. 다음 수열 값을 정해줄 때는 무조건 범위를 이전에 정해진 수열 값보다 큰 범위로 정해준다.(+1을 해준다.)

코드:

#include <iostream>
#include <algorithm>

using namespace std;

int arr[9] = {0,};

void dfs(int start, int count, int n, int m){
    if(count==m){
        for(int i=0;i < m;i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
    }else{
        for(int i=start;i<=n;i++){
            arr[count] = i; 
            dfs(i+1, count+1, n, m);//수열 중에 다음값을 선택한다.
        }
    }
} 

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;

    cin >> n >> m; //n까지의 자연수중, m개를 골라 만드는 수열

    dfs(1, 0, n, m);
    return 0;
}

감사합니다.