[백준 15652번] [Backtracking] N과 M(4)

Approach

이 문제를 단순히 반복문을 활용해서 처리하기 어려운 이유는 출력해야하는 자리수가 입력값에 영향을 받기 때문이다.

따라서 이 문제를 재귀를 통해 풀 수 있다는 것을 직관적으로 이해할 수 있다. 또한 증가하는 순서대로 출력해야한다는 조건 때문에 현재 입력하고 있는 값이 무엇인지 판단하는 것이 중요하다. 추가적으로 몇 번째 자리를 고려하고 있는 것인지 판단하는 것이 중요하게 된다.

따라서 재귀 함수의 입력값에 2가지 정보를 집어넣어주면 된다.

 

1. 현재 입력하고 있는 수

2. 현재 몇 번째 자리를 고려하고 있는지

 

추가적으로 이 문제는 출력값에 대한 배열을 따로 관리해주어야 한다.

그렇지 않으면 탑다운 방식으로 진행하는 상황에서 현재 숫자를 몇번이나 출력해야하는지를 알 수 없고, 재귀적으로 호출하는 것이 불가능하기에 자리수가 전부 다 채워지면 한번에 출력하는 방식을 채택해야 한다.

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
int result[8]; // Print value
int n, m;

void solve(int cur, int val){
    if(val == m){
        for(int i = 0; i < m; i++){
            cout << result[i] << " ";
        }
        cout << "\n";
        return;
    }
    for(int i = cur; i <= n; i++){
        result[val] = i;
        solve(i, val + 1);
    }
    return;
}

int main(void){
    fastio;
    cin >> n >> m;
    solve(1, 0);
    return 0;
}