[백준] 15665 : N과 M (11)

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

15665번: N과 M (11)

---

• 백트래킹으로 유명한 N과 M 시리즈 중 하나이다.
• 이번에는 각 자릿수마다 중복으로 값 선택이 가능하기 때문에 더 단순하게 각 재귀마다 N 번 반복해주면 된다.
• 다만 같은 수열을 중복 출력하는 것에 대한 검사가 필요하다.
• 각 자릿수마다 개별적인 방문 배열을 사용하여 현재 자릿수에서 뽑혔던 값인지를 확인해주자.
• ios_base::sync_with_stdio 를 사용했음에도 불구하고 시간 초과가 난다. 어이없어.. cstdio 쓰자

---

#include <cstdio>
#include <algorithm>

using namespace std;

int N, M;
int value[8];
int digit[8];

void pick(int cur)
{
    if(cur == M)                            // 자릿수 전부 다 골랐으면 출력
    {
        for(int i = 0 ; i < M ; i++)
        {
            printf("%d ", digit[i]);
        }
        printf("\n");
        return;
    }

    bool visited[10001] = {false,};         // 이번 자릿수의 중복 방지 배열
    for(int i = 0 ; i < N ; i++)            // 중복이 가능하므로 모든 가능한 값들을 탐색
    {
        if(visited[value[i]]) continue;     // 이전에 이미 검사됐던 값이면 스킵
        visited[value[i]] = true;
        digit[cur] = value[i];              // 현재 자릿수에 값을 넣어주고
        pick(cur + 1);                      // 다음 자릿수 재귀적으로 고름
    }
}

int main(void)
{
    scanf("%d %d", &N, &M);
    for(int i = 0 ; i < N ; i++)
    {
        scanf("%d", &value[i]);
    }
    sort(value, value+N);                   // 사전 순 출력을 위한 값 정렬

    pick(0);
}