[백준] 15666.cpp : N과 M (12)

www.acmicpc.net/problem/15666

15666번: N과 M (12)

---

• N과 M 시리즈 (9) 번 문제와 아주 유사한 문제로, 중복 허용이 추가되었다.
• 9번에서는 수열을 모두 저장한 후에 수열을 뽑았을 때 기존 수열들과 전부 비교하는 방식으로 풀었었는데, 이번 문제는 좀 더 효율적인 로직을 선택했다.
• 입력 값들이 모두 정렬되어 있는 상태이기 때문에 임의의 자릿수를 뽑을 때 직전에 뽑았던 데이터와 중복되면 넘어가고, 아닐 경우 직전 값을 갱신해주면 중복된 수열을 막을 수 있다.
• 값은 중복되어도 되기 때문에 같은 자릿수에서만 같은 값이 나오지 않게 처리해주면 된다.

---

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
int data[8];
int ans[8];

void check(int cur, int size)
{
    if(size == m)
    {
        for(int i = 0 ; i < m ; i++)        // m 개를 다 뽑았을 시 뽑은 값들 출력 후 종료
        {
            cout << ans[i] << " ";
        }
        cout << '\n';
        return;
    }
    
    int bef = 0;                            // 같은 자릿수의 값들 중에서는 같은 값이 나오지 않게
    for(int i = cur ; i < n ; i++)          // 중복이 허용되므로 시작은 현재 값부터
    {
        if(data[i] != bef)                  // 값들이 정렬되어있으므로, 직전에 뽑았던 값이 아닐 경우에만 실행
        {
            bef = data[i];
            ans[size] = data[i];            // 이번 자릿수 결정해주고
            check(i, size + 1);             // 다음 자릿수 뽑음
        }
    }
}

int main(void)
{
    cin >> n >> m;
    for(int i = 0 ; i < n ; i++)
    {
        cin >> data[i];
    }
    sort(data, data+n);

    check(0, 0);                            // 0 부터 시작
}