[백준 15655번] N과 M (9) (C/C++)

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

15663번: N과 M (9)

---

이번 문제는 전체 수열에 같은 값이 있을 때,  임의의 수열에 같은 수가 여러번 나올 수 있도록 하면서, 수열은 중복되지 않도록 하는 것이 핵심인 문제입니다. 

 

14와 17번째 라인이 핵심 코드입니다.

먼저, th번째 숫자를 선택할 때 vector에 저장합니다. 34번째 라인에서 전체 수열을 오름차순으로 정렬했기 때문에, 다음 수열을 결정할 때 vector의 back()을 확인해서 현재 선택하려는 숫자와 같으면 중복된 수열이므로, 선택하지 않습니다. 

 

예) 수열 = [2, 3, 4, 4, 9], M = 3, v = []

1. 1번째에 2을 선택, 2번째에는 3, 4, 4, 9를 선택할 수 있음
2. 2번째에 3을 선택 -> 수열 [2, 3, 4], [2, 3, 9], v = [3]
3. 2번째에 4를 선택 -> 수열 [2, 4, 3], [2, 4, 4], [2, 4, 9], v = [3, 4]
4. 2번째에 4를 선택 -> 현재 선택하려는 숫자가 4이고, v.back()이 4이기 때문에 선택 x
5. 2번째에 9를 선택 ...

이러한 방식으로 임의의 수열에 같은 수가 여러번 나올 수 있도록 하면서, 수열은 중복되지 않도록 할 수 있습니다.

전체 코드는 아래와 같습니다.

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

int n, m;
int arr[8];
int selected[8];
bool isused[8];

void back(int th){  // 수열의 길이가 (M + 1 - th)인 수열을 모두 구하는 함수
    if(th == m + 1){
        for(int i = 0; i < m; i++) cout << selected[i] << " ";
        cout << "\n";
    }else{
        vector<int> v;  // th번째에 선택한 숫자를 저장하는 벡터

        for(int i = 0; i < n; i++){
            if(!isused[i] && (v.size() == 0 || (v.size() > 0 && v.back() != arr[i]))){  
                v.push_back(arr[i]);
                isused[i] = true; selected[th - 1] = arr[i]; 
                back(th + 1);
                isused[i] = false; 
            }
        }
    }
}

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

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

    sort(arr, arr + n); // 수열이 사전 순으로 증가하는 순서로 출력되도록 정렬
    back(1);
}