[BOJ/백준 6603][C++] 로또

문제

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

 

문제 내용

각 테스트케이스 별로, k개의 숫자를 입력받아 그중에서 6개를 골라 수열을 만들면 되는 문제이다.

k개의 숫자는 오름차순으로 주어진다.

 

문제 풀이

N과 M문제와 많이 비슷한 유형으로, 백트래킹으로 풀면 되는 문제이다.

입력의 마지막이 0으로 주어진다는 점을 잘 처리하는게 중요한 부분이고, 이외에는 백트래킹 풀이와 똑같이 하면 된다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

vector<int> arr;
vector<int> result(6, 0);

int k;

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

    for (int i = before + 1; i < k; i++) {
        result[cnt] = arr[i];
        back(cnt + 1, i);
    }
}

int main() {
    do {
        cin >> k;
        arr.assign(k, 0);

        for (int i = 0; i < k; i++) {
            cin >> arr[i];
        }

        back(0, -1);
        cout << '\n';

    } while (k != 0);
}