BOJ 6603번 : 로또

입력받은 정렬된 array 에서 원소갯수가 6개인 독립집합을 모두 구하는 문제이다.

흠.... 문제에 '모든' 이라는 단어를 보고 처음든 생각은 브루트포스 또는 DFS(깊이우선탐색) 인데, 정렬되어있는 배열에서 순차적으로 6개를 선택하면 되므로 DFS알고리즘과 좀더 가까운듯 하다.

 

입력받은 배열이 [1,2,3,4,5,6,7]일때, 6개를 순차적으로 선택하는 방법으로 아래의 그림처럼 탐색하는 것이 먼저 떠올랐다.

음...... 느낌상 윗 레벨의 숫자가 결정되면, 가능한 원소의 갯수만큼 아래 레벨에서 선택하면 될듯 하다.

 

즉, 첫 숫자로 1을 선택하게 되면, 뒤에 더 올수 있는 원소의 갯수는 5개 일것이고, 2와 3이 올수 있을 것이다.

 

1 뒤에 올 숫자로 2를 선택하면, 뒤에 올 수 있는 원소의 갯수는 4개 일 것이고, 3과4가 가능할 것이다.

 

이처럼 윗 레벨의 원소가 결정되면, 아래 레벨의 숫자를 다시 결정하는 것의 반복인데, 가장 깊은 곳 부터 탐색 할 것 이므로 recursive 한 DFS를 사용하면 될것 이다.

 

<소스코드>

#include <iostream>
#include<string.h>
#include<algorithm>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int> arr;
vector<int> res(6);
//DFS fuction
void cur(int level, int start, int size) {
    if (level == 6) {
        for (int i = 0; i < 6; i++)
            cout << res[i] << ' ';
        cout << endl;
        return;
    }
    else {
        for (int i = start; i< size; i++) {
            res[level] = arr[i];
            cur(level + 1, i + 1, size);
        }
    }
}
 
int main() {
    int size = 0;
    while (1) {
        int tmp;
        cin >> size;
        if (!size) break;
        for (int i = 0; i < size; i++) {
            cin >> tmp;
            arr.push_back(tmp);
        }
        cur(0, 0, size);               //DFS
        cout << endl;
        arr.clear();
    }
}

문제 :

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

6603번: 로또