백준 15663 - N과 M(9) [C/C++]

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

문제 설명 및 입력 출력

 

 반성해야 하는 문제.. 쉬운 개념을 생각치 못하고 뱅뱅 돌다가 결국 시간을 많이 쓰고 해결했다...

 

 N과 M 시리즈 중 어려운 문제인 것 같고, 중복 수열의 출력을 피해야 하기 때문에 이를 어떻게 처리해주어야 할지 고민해주어야 한다.

 

 우선 백트래킹 알고리즘을 사용하여 인덱스 접근을 매번 새롭게 해주어야 하는 것은 이전의 N과 M 시리즈 문제 중에 비슷한 게 있었기 때문에 쉽게 떠올릴 수 있었다.

 

 문제는 중복 수열의 출력을 어떻게 피할 것이냐는 것... 생각보다 수학적으로 생각해보면 간단하게 피할 수 있었다.

 

 아무리 길이가 긴 수열이더라도, 그 특징 상 마지막 수만 다르다면 다른 수열이 되는 것에 주목해야 한다.

• 배열에 값들을 입력받은 후, 크기 순서대로 정렬해 놓은 다음 마지막 끝줄에 추가된 수만 내가 들고 있으면 어떨까?
• 다음 수열의 마지막 값에 넣는 값이 내가 들고 있는 이 값과 동일하다면 같은 수열이 아닐까?
  • 백트래킹 알고리즘을 사용하고 있기 때문에 그 loop 안에서 이 로직을 사용한다면 참이 될 것이다.
  • 이는 수열을 구성하는 모든 값을 일일이 비교하지 않아도 된다는 큰 장점이 있다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(int a, int b){
    return a<b;
}

int num, howmany, n;
int lst[9];
int check[9];
bool visited[9];
int result[9];

void Permutation(int len){
    if(len==howmany){
        for(int i=0;i<howmany;i++){
            cout << result[i] << " ";
        }
        cout << '\n';
    }
    else{
        int lastone = 0;
        for(int i=0;i<num;i++){
            if(check[i]==0 && lst[i] != lastone){
                result[len] = lst[i];
                check[i] = 1;
                lastone = lst[i];
                Permutation(len+1);
                check[i] = 0;
            }
        }
    }
}


int main() {
    cin >> num >> howmany;
    for (int i=0;i<num;i++){
        cin >> lst[i];
    }
    sort(lst,lst+num);
    Permutation(0);

    return 0;
}