[BOJ C++] 백준 15651번: N과 M (3)

 📚 문제

[BOJ C++] 백준 15651번: N과 M (3)
https://www.acmicpc.net/problem/15651

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• N과 M 시리즈는 조건에 만족하는 수열을 모두 출력하는 문제이다. 확률과 통계에서 배우는 순열, 조합, 중복순열, 중복조합을 구현한다고 생각하면 된다.
• 이번 N과 M (3)은 1~N의 숫자로 길이가 M인 수열을 만드는 문제이다. N과 M (1)과 달리 중복된 숫자도 허용한다. 즉, 방문 여부를 확인할 필요가 없으므로 visited 배열이 필요하지 않다.
• [BOJ C++] 백준 15649번: N과 M (1)
• 재귀함수(DFS)와 백트래킹 방식을 사용하여 구현한다. 자세한 구현 방법은 다음과 같다.

 

• 선택한 값을 저장하는 배열(arr)을 준비한다.arr[dep]는 배열의 (dep+1)번째에 삽입될 숫자를 저장한다.

 

• 반복문을 통해 1부터 N까지 숫자를 순회한다. 이번 문제에서는 숫자를 중복하여 사용할 수 있으므로 별다른 조건 없이 arr[dep]에 숫자 i를 바로 추가한다.
• arr 배열에 채운 수열의 길이가 M이 되면 모두 출력한 뒤 종료(return)한다.

---

 ⌨️ C++ 코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> arr(8);

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

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

    cin >> n >> m;
    dfs(0);
}