[백준 / c++ ] 15655. N과 M(6)

문제 ⭐️

- 소요 시간 ⏰: 21min

• n개의 자연수 중
• m개를 골라 만든 오름차순 수열

코드 💻

#include <iostream>
#include <algorithm>
#define MAX 9
using namespace std;

int n, m;
int input[MAX]; // 입력으로 주어지는 수(배열이 될)
int arr[MAX]; // 배열
int 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++){
        if(!isused[i]){
            arr[cnt] = input[i];
            isused[i] = true;
            
            bfs(cnt+1, i+1); // i+1한 값을 num으로 넘겨주면, input의 인덱스로 들어가 앞의 자리수(input[i])보다 더 큰 값(input[i+1])이 뒤에 온다.
            isused[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    
    for(int i = 0; i<n; i++){
        cin >> input[i];
    }
    
    sort(input, input+n); // 배열을 오름차순으로 정리
    
    bfs(0, 0); // 비교값을 같이 보냄

    return 0;
}

---

풀이 ✏️

N과 M(5) 에서 오름차순 조건이 추가되었다.

bfs 함수를 호출할 때 num값을 같이 넘겨준다.
그리고 for문에서 i값을 num부터 시작하게 한다.

그러면 input[num]의 값부터 arr에 들어간다.

---

구체적인 예 🎯

제일 처음, bfs(0,0) 호출

• num = 0
• arr[0] = input[0] 이 된다.

그 다음, bfs(cnt+1, num+1) 즉 bfs(1, 1)이 호출

• arr[1] = input[1] 이 된다. (i가 num+1 부터 시작되기 때문)

이것의 반복...