[백준] N과 M (9)_15663, N과 M (10)_15664

N과 M (9)

같은 숫자가 있을 수 있다.

중복해서 뽑아서는 안 된다. 

사전 순으로 출력해야 한다.

 

input이 다음과 같은 경우 

4 2

9 7 9 1  

-> 1 7 9 9 로 정렬 

 

if (prev == arr[i] || check[i]) continue; 

중복해서 뽑으면 안되니까 check 배열을 이용해서 확인해야 한다. 

ex) 1 1 은 x

같은 숫자가 있을 수 있지만, 중복되는 수열이 여러 번 출력되면 안되므로 prev 변수와 현재 수를 비교해야 한다.

첫 번째 9는 dfs에 들어가서 1, 7, 9 를 마저 고르지만  두 번째 9는 prev와 같으므로 그냥 지나간다. 

ex) 9 9 두 번은 x

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int N, M;
int arr[8], s[8], check[8];
 
void dfs(int cnt) {
    if (cnt == M) {
        for (int i = 0; i < M; i++) {
            cout << s[i] << " ";
        }
        cout << "\n";
        return;
    }
    int prev = -1;
    for (int i = 0; i < N; i++) {
        if (prev == arr[i] || check[i]) continue; 
        prev = arr[i];
        s[cnt] = arr[i];
        check[i] = 1;
        dfs(cnt + 1);
        check[i] = 0;
    }
}
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + N);
    dfs(0);
    return 0;
}

 

N과 M (10)

9번 문제에서 비내림차순이어야 한다는 조건이 추가됐다.

배열을 정렬한 뒤, dfs를 거칠때마다 숫자를 고르는 for문의 시작 위치를 1씩 더해준다. 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int N, M;
int arr[8], s[8];
 
void dfs(int cnt, int idx) {
    if (cnt == M) {
        for (int i = 0; i < M; i++) {
            cout << s[i] << " ";
        }
        cout << "\n";
        return;
    }
    int prev = -1;
    for (int i = idx; i < N; i++) {
        if (prev == arr[i]) continue;
        prev = arr[i];
        s[cnt] = arr[i];
        dfs(cnt + 1, i + 1);
    }
 
}
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + N);
    dfs(0, 0);
    return 0;
}