[백준] 15650 N과 M(2) (C++)

15650번: N과 M (2)

 solved.ac의 CLASS 4에 있는 문제이다. 문제를 풀고 나서, 사람들의 코드를 보았는데 꽤 깔끔하게 잘 푼 것 같아서 기록해본다.(설명은 다른 분들보다 훨 못하는 것 같다...) 예전에 재귀를 처음 배울 때 건드렸 보았던 문제인데, 그 땐 풀다가 포기했었다. 오늘 보니까 꽤 잘 풀렸다. 실력이 는 것 같다 ㅎㅎ (아님 말고)

 

---

풀이

  재귀함수를 이용하여 문제를 해결하였다. 재귀함수의 input값은 idx와 cnt이다. idx는 살펴보기 시작할 인덱스를 의미하고, cnt는 지금까지 n개의 숫자 중에서 몇 개를 선택하였는지 나타낸다.

 

 

cnt가 m이면 출력을 해야한다. 따라서, 1부터 n까지 중에서 선택된 수들을 출력한다.

 

 

cnt가 m이 아니면 선택해야하는 수가 더 남아있다는 뜻이다. idx보다 작은 값은 고려하지 않아도 되기 때문에, 반복문의 범위는 idx부터 n까지이다. 반복문을 통해 그 수를 선택하고, 재귀함수를 통해 계속 진행한다. 해당 작업이 끝나면 선택한 수를 다시 취소하여준다. 백트래킹 과정이다!

 

 

cf) idx보다 작은값을 고려하지 않아도 되는, 아니 고려하지 않아야 하는 이유는 다음과 같다. n이 4, m이 3인 경우를 생각해보자. 만약 1,3을 선택했고, idx가 4일 때, 2를 선택해버린다면(1,3,2순서로 선택) 1,2,3를 출력하게 된다. 그런데, 이는 앞에서 1,2,3순서로 선택했을 때 이미 출력한 값이기 때문에 겹치게 된다.

 

---

코드

#include <iostream>
#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
using ll = long long;

ll n, m;
ll selected[9]; //선택된 수는 값이1, 선택되지 않은 수는 값이 0이다.

void rec(ll idx, ll cnt) {
    if (cnt == m) { //m개의 수를 모두 선택한 경우 출력해야한다.
        for (ll i = 1; i <= n; i++) {
            if (selected[i]) cout << i << " ";
        }
        cout << endl;
        return;
    }
    for (ll i = idx; i <= n; i++) { //idx 이전의 수들은 볼 필요가 없다.
        selected[i] = 1;     //수 선택
        rec(i + 1, cnt + 1); //재귀 i를 선택했으면, 1부터 i까지의 수는 보지 않아도 된다.
        selected[i] = 0;     //수 선택 취소
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    
    rec(1, 0); //1부터 선택해야하므로 rec(1,0)이다.

    return 0;
}