백준 s2 15663 N과 M (9), s2 15664 N과 M(10) c++

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

 

풀이

다른 N과 M 문제들과 다르게, 중복되는 수가 수열로 주어질 수 있다.

ex) 9 7 1 9

이런 경우에는 

1

7

9

9와 9는 같은 수열이므로 한 번만 출력되어야 하고, 

1 7

...

9 9

대신 9와 9가 같이 선택되면 99 수열을 이룰 수 있다.

 

이를 해결하기 위해서는 같은 자리에 같은 숫자가 들어가는 경우를 방지하면 된다.

예를 들어

1 _ 

에서 빈 자리에 9가 한 번 들어가고, 그 다음에 9가 또 들어가는 건 똑같은 수열이므로 안 된다. 

 

그러나

_ _

에서 첫 번째 자리에 9가 들어가고, 두번째 자리에 9가 들어가는 것은 괜찮다. 서로 다른 자리에 똑같은 수가 들어가는 것은 괜찮다.

 

이 예외처리를 위해 for문으로 숫자를 넣을 때, 이전의 수와 같은지 아닌지를 체크하도록 하였다.

 

코드

/*boj s2 15663 N과 M (9)*/
#include <algorithm>
#include <iostream>
#define MAXN 105
using namespace std;

int N, M;
int arr[MAXN];
int ans[MAXN];
int used[MAXN];

void func(int k) { // [k]에 넣을 차례
    if (k == M) {
        for (int m = 0; m < M; m++) {
            cout << ans[m] << " ";
        }
        cout << "\n";
        return;
    }

    int tmp = 0;
    for (int i = 0; i < N; i++) {
        if (used[i]) continue;
        if (tmp == arr[i]) continue; // 똑같은 수를 또 넣음

        used[i] = true;
        ans[k] = arr[i];
        tmp = arr[i];
        func(k + 1);

        used[i] = false;
    }
}

int main(void) {
    ios::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);
}

 

---

 

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

15664번: N과 M (10)

 

풀이

위 문제와 다르게 비내림차순 이므로, used 대신 마지막에 썼던 숫자부터 차례대로 수를 넣어주면 된다.

 

코드

/*boj s2 15664 N과 M (10)*/
#include <algorithm>
#include <iostream>
#define MAXN 105
using namespace std;

int N, M;
int arr[MAXN];
int ans[MAXN];

void func(int k, int i) { // [k]에 넣을 차례, i번째 arr부터 넣을 차례
    if (k == M) {
        for (int m = 0; m < M; m++) {
            cout << ans[m] << " ";
        }
        cout << "\n";
        return;
    }

    int tmp = 0;
    for (int j = i; j < N; j++) {
        if (tmp == arr[j]) continue; // 똑같은 수를 또 넣음
        ans[k] = arr[j];
        tmp = arr[j];
        func(k + 1, j + 1);
    }
}

int main(void) {
    ios::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);
}