[백준 / c++ ] 15652. N과 M(4)

문제

코드

#include <iostream>
using namespace std;
#define max 9

int n, m;
int arr[max];
bool isused[max];

void bfs(int cnt, int num){
    
    if(cnt == m){
        for(int i=0; i<m; i++){
            cout << arr[i] << ' ';
        }
        cout << '\n';
        return;
    }
    
    for(int i= num; i<=n; i++){
        
        arr[cnt] = i;
        isused[i] = true;
        
        // 두번째 자리가 i부터 시작되도록 함
        bfs(cnt+1, i);
        
        isused[i] = false;
    }
}

int main(int argc, const char * argv[]) {
    cin >> n >> m;
    
    bfs(0, 1);
}

풀이

1) 중복 x, 오름차순 : num을 매개변수로 넘겨주고 i=num부터 시작한다.
bfs를 재호출할 때 num자리에 i+1을 넣어, i+1의 수가 다음에 오도록 한다.

2) 중복 o, 오름차순 : if(isused[i]) 를 지워 중복을 가능하게 한다.

본 문제는 중복을 허용하며 오름차순으로 나오게 만들어야한다.
그러므로 1) 코드에서 bfs 재호출 부분에 num 자리에 i을 넣어주면 된다.
그러면 i 수가 다음에 오며 중복이 가능해진다.

한줄평

갑자기 헷갈려서 n과 m 시리즈를 다시보며 정리했다.
cnt, num, i를 헷갈리지 않는 게 중요하다.

• cnt: 현재 탐색하고 있는 수열의 자리 ex) arr[0]는 첫번째자리 탐색중
• i: 수열에 들어가는 실제 수
• num: 수열의 수와 비교해주기 위해 사용하는 수