백준 15663 : N과 M(9)

문제 링크입니다 https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제였습니다. 이번에는 주어지는 N개의 자연수 중 같은 수가 있을 수도 있었습니다. 조건은 다음과 같고,

 

- N개의 자연수 중에서 M개를 고른 수열

 

이번 문제에서 중요한 조건은 출력 조건에서 "중복되는 수열을 여러 번 출력하면 안된다"는 조건이었습니다.

예를 들면, 아래와 같은 입력이 들어왔을 때,

 

Ex) N = 4, M = 2, N개의 수 : [ 9, 7, 9, 1 ]

 

4개의 수 중에서 2개를 고른 수열을 출력해야 합니다. 이때, 9가 2개 들어있다고 해서 '(1, 9), (1, 9)' 이렇게 두 번 출력하면 안 된다는 뜻입니다. 이와 같은 조건을 처리하기 위해서는 (1, 9)를 출력하고 나서 (1, ?)에서 '?'에 해당하는 수를 고를 때 바로 직전에 내가 골랐던 수와 똑같은 수를 또 고르면 안된다는 뜻으로 해석할 수 있고, 수를 고를 때마다 직전에 골랐던 수를 고르지 않도록 구현해야 했습니다. 자세한 문제 풀이 및 구현 방법은 코드와 주석을 참고해주세요!

 

※ 설명과 코드를 봐도 이해가 되지 않으신다면 꼭 한줄한줄 디버깅을 해보시는 것을 추천합니다.

 

 

[소스코드]

 

#include<algorithm>
#include<iostream>
using namespace std;
 
bool check[8]; // 중복된 수를 고르지 않기 위한 배열
int n, m, num[8], result[8];
 
// 입력받은 n개의 수들 중에서 골랐던 수열과 똑같은 수열을
// 고르지 않게 m개를 고르고 출력해주는 함수
void getResult(int count) {
 
    // m개를 골랐다면 출력합니다
    if (count == m) {
        for (int i = 0; i < m; i++)
            cout << result[i] << ' ';
        cout << '\n';
        return;
    }
    // prev_num에 직전에 골랐던 수를 저장합니다 이 변수를
    // 전역변수로 선언하지 않고 이 곳에 선언하여 계속 
    // 초기화가 되도록 해주는 이유는 맨 처음에 고르는 수는
    // 직전에 골랐던 수와 관계없이 고르기 위함입니다
    int prev_num = -1;
    // 또한 함수의 재귀 호출이 출력으로 인해 끝나게 되면
    // for문 안에서 다음 수를 고르게 되는데 그 때
    // prev_num에 저장된 수를 고르지 않기 위함입니다
    for (int i = 0; i < n; i++) {
        
        // 직전에 골랐던 수가 아니고 이미 고른 수가 아니라면
        if (!check[i] && prev_num != num[i]) {
            
            check[i] = true;          // 골라주고
            result[count] = num[i];   // 배열에 넣고
            prev_num = num[i];        // 직전에 고른 수에 저장
            getResult(count + 1);     // 다음 수를 고르러 갑니다
            check[i] = false;
        }
    }
}
 
int main(void) {
 
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> num[i];
 
    // 수열은 사전 순으로 출력해야 하므로
    // 입력을 받고 오름차순으로 정렬합니다
    sort(num, num + n);
 
    getResult(0);
    return 0;
}