[BOJ C++] 백준 15652번: N과 M (4)

 📚 문제

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

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

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

 

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

 

• 반복문을 통해 1부터 N까지 숫자를 순회한다. 이번 문제에서는 숫자를 중복하여 사용할 수 있으므로 방문 여부와 상관없이 arr[dep]에 숫자 i를 바로 추가할 수 있지만, 비내림차순을 만족해야하므로 배열에 이미 저장되어있는 수보다 큰 수만 저장할 수 있다. 따라서 i가 arr[dep -1]보다 큰 숫자라면 arr[dep]에 숫자 i를 추가한다.
• arr 배열에 채운 수열의 길이가 M이 되면 모두 출력한 뒤 종료(return)한다.

---

 ⌨️ C++ 코드

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

int n, m;
vector<int> rst(9);

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

    for (int i = 1; i <= n; i++) {
        if (dep == 0) rst[dep] = i; // 배열의 맨 앞에 들어가는 경우.
        else if(rst[dep - 1] <= i) rst[dep] = i;
        else
            continue;
        dfs(dep + 1);
    }
}

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

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

 

문제의 설명과 달리 배열의 이름이 arr가 아니라 rst이다. 이름만 다를 뿐, 풀이 방법은 동일하다.