[BOJ/백준 15654][C++] N과 M (5)

문제

https://www.acmicpc.net/problem/15654

 

문제 내용

입력받은 N개의 자연수 중에 M개를 골라 수열을 만들어 출력하면 된다.

이때 수열을 사전순으로 증가하는 순서대로 출력해야 한다.

 

문제 풀이

N과 M (1)과 다르게 N과 M (5)는 N개의 원소를 입력으로 받아와야 한다는 차이가 있다.

입력은 정렬된 상태로 주어지지 않기 때문에, backtracking을 하기 전에 정렬을 해줘야 한다.

[BOJ/백준 15649][C++] N과 M (1)

 

코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int n, m;

vector<int> result(8, 0);
vector<int> arr;
vector<bool> used(8, false);

void back(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << result[i] << ' ';
        }
        cout << '\n';
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            used[i] = true;
            result[cnt] = arr[i];
            back(cnt + 1);
            used[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    arr.assign(n, 0); // 여기서 초기화를 크기 n만큼 초기화를 할 것

    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());

    back(0);
}

 

문제 코드 설명

arr을 전역배열로 크기 선언을 하지 않고, main에서 assign을 통해 한 이유는, 정렬을 arr.end()까지 했을 때 앞부분이 0으로 채워지기 때문이다. 

vector<int>arr(8,0) 이런 식으로 전역배열로 선언할꺼라면, sort 할 때 arr.end()가 아닌 입력받은 n만큼으로 설정해줘야 한다.