백준 15652번, N과 M(4)

백준 15652번 c++ 문제풀이

문제:

백준 15652

풀이:

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

코드:

#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, 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;
}

감사합니다.