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

‡ CODING TEST STUDY ‡/º 백준

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

Trudy | 송연 2023. 9. 1. 19:37

15650번: N과 M (2)

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해

www.acmicpc.net

내가 처음 작성한 문제의 코드는

#include <iostream>
#include <vector>

using namespace std;

int m;
vector<int> v;
int a[8];

void dfs(int start, int depth){
    if(depth == m){
        for(int i=0; i<m; i++){
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    for(int i = start; i<m; i++){
        a[i] = v[i];
        dfs(i+1, depth+1);
    }
}

123
dfs(0,0) dfs(1,1) 

int main(){
    int n;
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        v.push_back(i);
    }
    
    dfs(0,0);
    
    return 0;
}

출력 결과가 한 줄만 나와서 고민을 하다가 문제의 코드를 찾아냄

밑에 사람도 비슷하게 풀었길래

[백준(BOJ)] 15650번 : N과 M (2) - C++[CPP] (tistory.com)

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

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

tooo1.tistory.com

void dfs(int start, int depth){
    if(depth == m){
        for(int i=0; i<m; i++){
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    for(int i = start; i<n; i++){
        a[depth] = v[i];
        dfs(i+1, depth+1);
    }
}

여기에서 두번째 for문의 범위를 i<n으로 바꿔줬고,

a[i]=v[i]가 아닌, a[depth]=v[i]로 바꿔줬다.

그렇게 완성된 최종 코드는

#include <iostream>
#include <vector>

using namespace std;

int n, m;
vector<int> v;
int a[8];

void dfs(int start, int depth){
    if(depth == m){
        for(int i=0; i<m; i++){
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }
    
    for(int i = start; i<n; i++){
        a[depth] = v[i];
        dfs(i+1, depth+1);
    }
}


int main(){
    cin >> n >> m;
    
    for(int i=1; i<=n; i++){
        v.push_back(i);
    }
    
    dfs(0,0);
    
    return 0;
}