(C++) 백준 15649번 - N과 M (1)

 

문제 링크 : https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

풀이

백트래킹을 사용한 풀이이다.

이미 특정 숫자가 배열에 들어가 있는지 arr을 순회하면서 확인하고, 들어있지 않은 숫자들만 배열에 삽입한다.

사이즈가 m이 되는 순간 지금까지 배열에 저장해 놓은 숫자들을 출력한다.

#include <iostream>

using namespace std;

int n, m;
int arr[8];

void nNm(int num, int idx){
    for(int x = 0; x < idx; ++x){ // 중복 요소 검증
        if(arr[x] == num) return;
    }
    arr[idx] = num;
    if(idx == m-1){ // base condition
        for(int x = 0; x < m; ++x){
            cout << arr[x] << " ";
        }
        cout << "\n";
        return;
    }
    for(int x = 1; x <= n; ++x){
        nNm(x, idx+1);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    cin >> n >> m;

    for(int i = 1; i <= n; ++i){
        nNm(i, 0);
    }
}

arr를 모두 순회하면서 사용했는지 체크하는 것은 O(n)의 시간복잡도를 가지기에 이보다 더 간단한 방식을 찾아보았다.

isUsed라는 이미 방문했는지 체크(O(1)의 시간복잡도)하는 배열을 선언하여 이를 사용하여 다시 구현해 보았다.

확실히 위의 방법보다 시간이 줄었음을 채점 시간을 통해 확인할 수 있었다.

#include <iostream>

using namespace std;

int n, m;
int arr[8];
int isUsed[9];

void nNm(int idx){
    if(idx == m){ // base condition
        for(int x = 0; x < m; ++x){
            cout << arr[x] << " ";
        }
        cout << "\n";
        return;
    }
    for(int x = 1; x <= n; ++x){ // x를 1부터 n까지 순회하며
        if(!isUsed[x]){ // x가 사용되지 않았다면
            arr[idx] = x; // 배열에 삽입하고
            isUsed[x] = 1; // 사용되었다고 표시
            nNm(idx+1); // base condition이 될때까지 백트래킹
            isUsed[x] = 0; // 사용이 끝났으므로 0으로 표시
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    cin >> n >> m;

    nNm(0);
}