15663번 - N과 M(9)

📌문제

👉 문제보기

코드

#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;

int n, m;
int arr[MAX];
int ans[MAX];
bool visited[MAX];

void dfs(int depth) {
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << ans[i] << " ";
        }
        cout << '\n';
        return;
    }

    int end = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i] && arr[i] != end) {
            visited[i] = true;
            ans[depth] = arr[i];
            end = arr[i];
            dfs(depth + 1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr, arr + n);

    dfs(0);

    return 0;
}

🍳문제 풀이

이번 문제는 고민을 조금 했던 것 같다.
단순하게 입력 값 중에 중복을 없애면 된다고 생각했다. 그러나 예제 2번을 보면,

예제 입력
4 2
9 7 9 1

예제 출력
1 7
1 9
7 1
7 9
9 1
9 7
9 9

이 경우, 9 9의 출력이 불가능함을 알 수 있다.

따라서 해결 방법은, 이전에 추가한 값을 미리 저장해놓고 하면 된다.
이전에 추가한 값을 end에 저장해 놓고, 호출한 dfs가 끝나게 되면 end 변수와 같지 않은 숫자들만 배열에 추가한다.

---

15664번 - N과 M (10)

📌문제

👉 문제보기

코드

입력 받는 부분은 제외

void dfs(int index, int depth) {
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << ans[i] << " ";
        }
        cout << '\n';
        return;
    }
    
    int before = 0;
    for (int i = index; i < n; i++) {
        if (!visited[i] && arr[i] != before) {
            visited[i] = true;
            ans[depth] = arr[i];
            before = arr[i];
            dfs(i + 1, depth + 1);
            visited[i] = false;
        }
    }
}

🍳문제 풀이

N과 M(9) 문제와 마찬가지로 이전 값을 저장해 놓고, 같지 않은 경우에만 출력하면 된다!
비내림차순이 조건이므로 이전에 출력하는 index값을 dfs 파라미터로 전달하면 풀 수 있다

---

15665번 - N과 M (11)

📌문제

👉 문제보기

코드

void dfs(int depth) {
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << ans[i] << " ";
        }
        cout << '\n';
        return;
    }

    int before = 0;
    for (int i = 0; i < n; i++) {
        if (arr[i] != before) {
            ans[depth] = arr[i];
            before = arr[i];
            dfs(depth + 1);
        }
    }
}

🍳문제 풀이

같은 수를 여러 번 골라도 되는 중복 순열이다.
visited 방문 체크를 하지 않고, 이전에 추가한 값과 같지 않으면 된다.
N과 M (9)와 N과 M(10)과는 다르게 같은 수를 여러 번 골라도 되므로, 입력 값에서 중복을 제외한 뒤에 N과 M(7) 같이 풀어도 된다 !

중복 제외
vec.erase(unique(vec.begin(), vec.end()), vec.end());
unique를 실행하면 중복된 값들이 뒤로 밀려나고, 중복되지 않은 vector의 맨 마지막 iterator를 반환.

---

15666번 - N과 M (12)

📌문제

👉 문제보기

코드

void dfs(int depth) {
    if (depth == m) {
        for (int i = 0; i < m; i++) {
            cout << ans[i] << " ";
        }
        cout << '\n';
        return;
    }

    int before = 0;
    for (int i = 0; i < n; i++) {
        if (before != arr[i] && ans[depth - 1] <= arr[i]) {
            ans[depth] = arr[i];
            before = arr[i];
            dfs(depth + 1);
        }
    }
}

🍳문제 풀이

중복 순열에 비내림차순이 조건이다.
이전에 추가된 값인 ans[depth - 1]과 비교하여 같거나 큰 경우에 ans배열에 추가해준다.