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

백준 문제 풀이: 15652 [N과 M (4)]

---

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

문제 설명:

1부터 N까지 자연수 중에서 중복을 허용하여 M개를 고른 수열을 출력하는 문제입니다. 단, 수열은 비내림차순이어야 합니다.

입력:

• 첫째 줄에 자연수 N과 M이 주어집니다. (1 ≤ M ≤ N ≤ 8)

출력:

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

---

문제 해결 코드

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

int n, m;
vector combination;

void dfs(int start) {
    if (combination.size() == m) {
        for (int num : combination) {
            cout << num << " ";
        }
        cout << '\n';
        return;
    }

    for (int i = start; i <= n; i++) {
        combination.push_back(i);
        dfs(i); // 중복 허용: 현재 숫자를 다시 선택 가능
        combination.pop_back();
    }
}

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

    cin >> n >> m;

    dfs(1);

    return 0;
}

예제

입력:
4 2

출력:
1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

---

코드 설명

• DFS 탐색:
  • 현재까지 선택된 숫자를 저장하는 벡터 combination을 활용합니다.
  • DFS의 시작 인덱스를 고정하거나 증가시키며 비내림차순을 유지합니다.
• 기저 조건:
  • combination의 크기가 M에 도달하면 현재 조합을 출력합니다.
• 백트래킹:
  • DFS 호출 후 combination의 마지막 숫자를 제거하여 이전 상태로 복구합니다.

시간 복잡도

• N개의 숫자에서 M개를 선택하며 중복을 허용하므로 시간 복잡도는 O(N^M)입니다.
• 최대 N과 M이 8이므로 계산량은 충분히 처리 가능합니다.

---

결과

코드는 입력된 N과 M에 따라 모든 비내림차순 조합을 출력하며, DFS와 백트래킹을 통해 효율적으로 구현되었습니다.

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