백준 15654번 [N과 M (5)](C++)-yes6686- 티스토리

백준 문제 풀이: 15654 [N과 M (5)]

---

문제 링크: https://www.acmicpc.net/problem/15654

문제 설명:

1부터 N까지 자연수 중에서 M개를 고른 수열을 출력하는 문제입니다. 입력으로 주어지는 N개의 숫자 중 M개를 고르며, 수열은 사전순으로 증가하는 순서로 출력해야 합니다.

입력:

• 첫째 줄에 자연수 N과 M이 주어집니다. (1 ≤ M ≤ N ≤ 8)
• 둘째 줄에 N개의 자연수가 주어집니다. (1 ≤ r[i] ≤ 10,000)

출력:

• 한 줄에 하나씩 조건을 만족하는 수열을 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int arr[8];
int r[8];
bool visited[8];

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

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;

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

    sort(r, r + n); // 입력값 정렬

    dfs(0);

    return 0;
}

예제

입력:
4 2
9 8 7 1

출력:
1 7
1 8
1 9
7 8
7 9
8 9

---

코드 설명

• 입력 정렬:
  • 입력 배열을 정렬하여 사전순으로 출력이 가능하도록 합니다.
• DFS 탐색:
  • 현재까지 선택된 숫자를 저장하는 배열 arr를 사용합니다.
  • 숫자를 선택할 때, 이미 사용된 숫자는 visited 배열로 체크하여 중복을 방지합니다.
• 기저 조건:
  • 선택된 숫자의 개수가 M개에 도달하면 현재 수열을 출력합니다.

시간 복잡도

• DFS의 시간 복잡도는 O(N!/(N-M)!)이며, 최대 N이 8이므로 충분히 처리 가능합니다.

---

결과

코드는 주어진 조건을 만족하며, 입력된 숫자로 사전순으로 정렬된 모든 수열을 정확히 출력합니다. 문제의 제약 조건 내에서 효율적으로 동작합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!