문제 푼 날짜 : 2021-09-16

문제

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

접근 및 풀이

중복조합에 관한 문제였다.
15650번 문제에서 같은 수를 여러 번 골라도 된다는 조건이 추가되었다.
결국 중복 조합을 구현하는 문제였고, 15650번 풀이에서 숫자를 선택했는지 여부를 나타내는 visited 배열과 이에 해당하는 로직을 삭제하였다.

코드

#include <iostream>

using namespace std;

int N, M;
int number[9];

void dfs(int num, int cnt) {
    if (cnt == M) {
        for (int i = 0; i < M; i++) {
            cout << number[i] << ' ';
        }
        cout << '\n';
        return;
    }
    for (int i = num; i <= N; i++) {
        number[cnt] = i;
        dfs(i, cnt + 1);
    }
}

int main()
{
    cin >> N >> M;
    dfs(1, 0);
    
    return 0;
}

결과

피드백

백트래킹에 대한 개념이 점점 잡혀가는 것 같다.