[백준 알고리즘/BOJ/C++] 15649 N과 M (1)

 

 

자연수 N과 M이 주어졌을 때, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열을 출력하는 문제

 

N=3, M=1 일 때

1

2

3

 

N-4, M=2 일 때

1 2

1 3

1 4

2 1

2 3

2 4

3 1

3 2

3 4

4 1

4 2

4 3

 

이렇게 출력하면 된다

 

백트래킹은 조건에 만족할 경우 모든 경우의 수를 살펴보는 것 이라고 한다

N과 M (1)에선 중복이 아닐 경우(조건) 모두 출력한다 정도로 생각하면 될 것 같다

 

 

수열을 저장할 배열과 중복인지 체크할 배열을 각각 만들었다

배열에 저장한 수가 M개면 출력하고, 아니라면 중복인지 체크해서 배열에 수를 넣어주면 된다

 

 

#include <iostream>
using namespace std;
 
int n, m;
int arr[10];
bool isused[10];
 
void func(int k) {
    if (k == m) { //M개의 수 출력
        for (int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
 
    for (int i = 1; i <= n; i++) {
        if (!isused[i]) {
            arr[k] = i;
            isused[i] = 1;
            func(k + 1);
            isused[i] = 0;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n >> m;
    func(0);
}

 

arr는 수열을 저장할 배열, isused는 중복을 체크하는 배열

 

백트래킹의 기본이라는데 어려웠던 기억ㅎㅎ..