15663번: N과 M (9) (BOJ C/C++)

15663번: N과 M (9)

사용 언어: C++

 

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

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

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

풀이 1

하나의 수열을 일단 만들면 tmp는 가장 마지막에 만든 수열의 마지막 항을 저장하는데 수열을 만든 후 다음 수열의 마지막 항과 비교해서 같으면 중복으로 판단해 출력되지 않는다. 예를 들어 숫자들이 n=4 m=2, 1 2 2 9면 수열 1 2 를 만들면서 tmp = 2가 저장되고 그 이후에 다른 수열을 만들 것이다. 다른 수열이 만들어지면서 tmp=2와 num[i]에 저장된 중복된 2와 비교하면서 tmp != num[i]에 대입해보면 2 != 2여서 중복된 수열이 만들어지지 않는다.

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

int n, m;
int arr[10];
int num[10];
bool isused[10];

void func(int cur){
    if(cur == m){
        for(int i=0; i<m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    int tmp=0;
    for(int i=0; i<n; i++){
        if(!isused[i] && tmp != num[i]){//중복 없게 이전 수열과 현 수열 비교
            isused[i] = 1;
            tmp = arr[cur] = num[i];
            func(cur+1);
            isused[i] = 0;
        }
    }
}

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

    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> num[i];
    sort(num, num+n);
    func(0);

    return 0;
}

 

풀이 2

좀 더 직관적인 풀이로 num[i]의 값에 해당하는 index를 가진 bool check을 만들어서 이미 썼으면 check[num[i]]로 넘기는 풀이다.

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

int n, m;
int arr[10];
int num[10];
bool isused[10];

void func(int cur){
    if(cur == m){
        for(int i=0; i<m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    bool check[10000] = {0,};
    for(int i=0; i<n; i++){
        if(!isused[i] && !check[num[i]]){
            check[num[i]] = 1;
            isused[i] = 1;
            arr[cur] = num[i];
            func(cur+1);
            isused[i] = 0;
        }
    }
}

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

    cin >> n >> m;
    for(int i=0; i<n; i++) cin >> num[i];
    sort(num, num+n);
    func(0);

    return 0;
}