[백준 15664번] N과 M (10) (C++)

문제링크 : https://www.acmicpc.net/problem/15664

15664번: N과 M (10)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = INT_MAX;

int N, M, arr[9], result[9];

void func(int cnt, int idx)
{
    if(cnt==M)
    {
        for(int i=0; i<M; i++) cout << result[i] << " ";
        cout << "\n";
        return;
    }
    else
    {
        int prev = 0;
        for(int i=idx; i<N; i++) //백트래킹
        {
            if(prev == arr[i]) continue; //직전 값 체크
            result[cnt] = prev = arr[i];
            func(cnt+1, i+1); //카운팅, 인덱스 증가
        }
    }
}

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

    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];
    sort(arr, arr+N); //정렬
    func(0, 0);

    return 0;
}

 

중복 수열을 검사해야하는 백트래킹 문제이다.

이를 위해 직전 값이 현재 값이란 같은 경우인지 체크를 해준다.

직전 값과 다르다면 수열 배열 및 직전 값을 현재 값으로 갱신해준다.

 

이후 카운팅과 인덱스를 하나씩 증가시켜서 카운팅이 M과 되는 순간에 출력을 해주고,

아니라면 현재 인덱스를 기준으로 위 과정을 반복해준다.