백준 15663. N과 M (9) (백트래킹)

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

15663번: N과 M (9)

이전에 풀어봤던 문제인데, 백트래킹이랑 next_permutation을 이용한 순열 문제를 잘 못푸는 거 같아서 한번 더 풀고 정리했다. 

 

1. 백트래킹 코드

arr = {1, 7, 9, 9} 이고 4개중 2개를 뽑는다고 가정하자. 이 때 {1, 9(첫번째)}, {1, 9(두번째)}는 같은 것이다. 

tmp를 설정해서 이번 순회에서의 arr[i]값을 저장하고, i가 1 증가했을 때, arr[i] (앞의 i를 기준으로 한다면 arr[i+1])이 앞의 값(tmp)와 같으면 이번 순회는 건너뛴다.

#include <string>
#include <algorithm>
#include <iostream>
#include <limits.h>
using namespace std;

int n, m;
int arr[10];
int ans[10];
int vis[10];
void func(int cur)
{
    if(cur == m)
    {
        for(int i = 0; i < m; i++)
            cout << ans[i] << ' ';
        cout << '\n';
        return;
    }
    int tmp = 0;
    for(int i = 0; i < n; i++)
    {
        if(vis[i] == true) continue;
        if(arr[i] == tmp) continue;
        vis[i] = true;
        tmp = arr[i];
        ans[cur] = arr[i];
        func(cur+1);
        vis[i] = false;
    }
}

int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    sort(arr, arr+n);
    func(0);

    
}

 

2. next_permutation 

{1,7,9,9}가 들어오면 다음과 같은 배열이 next_permutation에 의해 만들어진다. 

1799 1979 1997

7199 7919 7991

9179 9197 9719 9791 9917 9971 

앞의 두자리만 뽑고 싶다고 가정하면, 처음에 출력하는 배열을 prev 배열에 저장하고, 그 다음 번에는 앞의 출력과 다른 값일 때만 출력하면 된다. 

 

next_permutation으로 딱 맞아떨어지게 풀 수 있는 방법이 있는 줄 알았는데, 풀다보니,,,, 안된다는 걸 알았다. 지저분하게 풀긴 풀었다. 

#include <string>
#include <algorithm>
#include <iostream>
#include <limits.h>
using namespace std;

int n, m;
int arr[10];
int tmp[10];
int prevarr[10];

int main()
{
    cin >> n >> m;

    for(int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    sort(arr, arr+n);

    int isT = 0;
    do
    {
        isT = 0;
        for(int i = 0; i < m; i++)
        {
            tmp[i] = arr[i];
        }

        for(int i = 0; i < m; i++) // 이번에 나온 배열과 저번에 나온 배열이 같은지 확인
        {
            if(prevarr[i] == tmp[i])
            {
                isT+=1;
            }

        }

        if(isT != m) // 같지 않다면, 이전 배열에 이번 값 저장하고, 이번 값 출력
        {
            for(int i = 0; i < m; i++)
            {
                cout << tmp[i] << ' ';
            }
            cout << '\n';

            for(int i = 0; i < m; i++)
            {
                prevarr[i] = tmp[i];
            }
        }

        

    }while(next_permutation(arr, arr+n));
    
}