문제 푼 날짜 : 2021-09-15

문제

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

접근 및 풀이

백준 15649번 문제와 비슷했지만, 중복을 허용하지 않는다는 점이 달랐다. 즉, 조합을 구현하는 것이 핵심이다.
이를 해결하기 위해, 이전에 방문된 숫자는 선택하지 않도록하는 매개변수(코드 내 num)를 두었다.
재귀로 조합을 구현하는 것은 https://yabmoons.tistory.com/99 이 곳에 아주 설명이 잘되어 있어서 푸는데 도움이 되었다.

코드

#include <iostream>

using namespace std;

int N, M;
int number[9] = { 0, };
bool visited[9] = { false, };

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++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        number[cnt] = i;
        dfs(i, cnt + 1);
        visited[i] = false;
    }
}

int main() {
    cin >> N >> M;

    dfs(1, 0);
    return 0;
}

결과

피드백

백트래킹 문제를 더욱 많이 풀어서 사고하는 연습을 하자.