[BOJ] N과 M(1), next_permutation풀이

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

백트래킹으로 푸는걸 떠나서, next_permutation으로 어떻게 풀어야 할지 감이 잘 오지 않았다.

코드를 짧게해서 조합을 구할때처럼 뭔가 깔끔한 N! 풀이가 없나? 싶었다.

조합은 {0,0,0,1,1}로 두고 5C3을 한번에 출력할 수 있지만, 순열은 그렇지 않다.

​

특히 next_permutation은 5명중에 순서고려 X해서 5명 다 세우는건 쉽게 할 수 있다.

하지만, 4P2 이런건 어떻게할지 막막했다. 중복이 생겼기 때문이다.

1 2 3 4

1 2 4 3 에서 보면 1,2가 2번 출력된다. 이걸 깔끔하게 걸러내고 싶었다.

​

next_permutation 풀이를 검색해도 나오질 않았다. 다들 쉬운 조합을 구하는 N과 M(2)에서만 썼었다.

​

생각해보니까 굉장히 간단하게 4P4 출력하듯이 출력 할 방법이 있었다.

(이전의 출력값과 같으면 그냥 넘어가면 됐었다.)

​

코테에서 이걸 쓰면 좀 더 편하게 백트래킹 없이 순열을 구할 수 있으니 익혀둬야겠다고 생각했다.

​

// 1,2,5,6 next permu가능
    #include<bits/stdc++.h>
    using namespace std;
    int arr[10];
    int pre[10];
    int main(void)
    {
        // n! n
        ios::sync_with_stdio(0);
        cin.tie(0);
        int n,m,flag;

        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;
                }
            }
            if(!flag){
                continue;
            }
            for(int i = 0; i < m; i++)
            {
                cout << arr[i] << " ";
                pre[i] = arr[i];
            }
            cout << "\n";
        }while(next_permutation(arr,arr+n));
        
        return 0;
    }

시간복잡도는 O(N!)이다.

​

1 2 3 4 , 1 2 4 3 에서 앞의 2개를 고르면 1,2 가 2번이 나온다.

출력할때 pre에다가 1,2를 저장해두면

1,2,3,4 에서 pre = {1,2} 가 들어가고

1,2,4,3 에서 pre = {1,2} 때문에 출력하지 않고 넘어가게 된다.

그 다음 1 3 2 4 에서 출력을 하면서 pre = {1,3}으로 바꿔주면 된다.

​

굿

​

정리.

1. 모든 순열을 출력하면 next_permutation 좋다.

2. 조합을 출력할땐 0과 1로..

3. 숫자가 오름차순으로 sort가 되어있어야한다.

4. 중복을 포함하면 사용하기 힘들다. 1 1, 1 2, 1 3 , 2 1, 2 2 이런건 출력하기 힘들다. (next_permutation이 중복을 건너뛴다)

​

끝

감사합니다