[백준] 15649번. N과 M (1)

[백준] 15649번. N과 M (1)

1. 문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

2. 입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

3. 출력

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

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

4. 풀이

• 재귀를 활용했다.
• m개가 선택되면 출력을 한다.
• m개가 선택이 되지 않았으면 아직 선택 안 된 숫자를 넣고 count를 증가 시킨 후 재귀를 한다.
• 함수가 끝나면 다시 선택을 해제하고 count를 줄인다.

5. 처음 코드와 달라진 점

• 출력을 할 때 현재 숫자보다 작은 숫자를 출력하지 않았다.
• bool 배열만 이용하는 방식에서 vector를 이용해서 현재 숫자의 순서까지 넣었다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

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

void print() {
    for (int i = 0; i < v.size(); i++){
        cout << v[i]+1 << " ";
    }
    cout << "\n";
}

void dfs(int count) {
    if (count == m) {
        print();
    }
    else {
        for (int i = 0; i < n; i++){
            if (!arr[i]) {
                arr[i] = true;
                v.push_back(i);
                count++;

                dfs(count);
                arr[i] = false;
                v.pop_back();
                count--;
            }
        }
    }    
}

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

    cin >> n >> m;

    dfs(0);
}