백준 15649 N과 M(1)

백트래킹 이용

• 중복을 허락하지 않는 순열을 출력하는 문제이다.
• 수열을 담을 배열 설정
• 중복 체크할 배열 설정
• 배열의 수가 m개가 되면 출력
• 아니면 1~n까지의 수 중 중복이 아닌 수를 찾아 배열에 삽입

#include <bits/stdc++.h>
using namespace std;

int n, m;

int arr[10]; // 수열 담을 배열
int isUsed[10]; // 중복 체크 배열

void func(int cnt) {
    if(cnt == 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[cnt] = i;
            isUsed[i] = 1;
            func(cnt+1);
            isUsed[i] = 0;
        }
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    func(0);
}

next_permutation 사용

• next_permutation을 사용한다.

#include <bits/stdc++.h>
using namespace std;

int n, m, flag;
int arr[10], pre[10];

int main(void) {
	ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for(int i = 0; i < n; i++) arr[i] = i+1;
    sort(arr, arr+n);
    do {
    	flag = false;
        for(int i = 0; i < m; i++) {
        	if(pre[i] != arr[i]) {
            	flag = true;
                break;
            }
        }
        // pre와 arr가 같다면 continue;
        if(!flag) continue;
        for(int i = 0; i < m; i++) {
        	cout << arr[i] << ' ';
            // 출력한 값을 pre에 넣고 다음 출력할 때 비교하는 과저을 통해 중복을 막는다.
            pre[i] = arr[i];
        }
        cout << '\n';
    } while(next_permutation(arr, arr+n));
}