# 백준 : 로또(6603)

문제

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

소스

(Github: https://github.com/wonjnlee/wallydev/blob/master/bj_6603_lotto)

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <cmath>
using namespace std;

int totalcount;
int visits[15];
int vertex[15];


void visiting(int current, int count) {
    if((current == totalcount) && (count == 6)) {
        for(int i=0; i<totalcount; i++) {
            if(visits[i])   cout<<vertex[i]<<" ";
        }
        cout<<endl;
    }
    else {
        if(current == totalcount) return;
        else {
            visits[current] = 1;
            visiting(current + 1, count + 1);
            visits[current] = 0;
            visiting(current + 1, count);
        }
    }
}

int main(void)
{
    while(1) {
        cin>>totalcount;
        if(totalcount == 0) break;
        else {
            for(int i=0; i<15; i++) visits[i] = 0;
            for(int i=0; i<totalcount; i++) cin>>vertex[i];
            visiting(0,0);
        }
        cout<<endl;
    }
    return 0;
}

풀이

알고리즘 보기에 DFS를 보고 이 방법으로 접근했다가 완전히 '패망'했다.
솔직하게 말하면 '이곳'을 참조하였는데, 굉장히 신박하고 색다른 방법이라고 생각한다.

내가 처음에 세운 '실패한' 알고리즘은
1. 먼저 DFS로 하나씩 구하고
2. 그 내용들을 추후에 sorting해서
3. sorting한 내용이 혹시 존재하는지 확인하는 방법
이었는데, 이렇게 하면 제한시간 1초안에 해결도 불가능할뿐더러 실제 코드도 엄청 지저분해질 것이다.

이분은 다음과 같이 접근하였는데,
1. 어차피 맨 뒤의 숫자만 바뀌는 것
2. 순서대로 쭉 늘여가거나 아니면 지금 접근한 녀석은 카운트하지 않고 다음 녀석으로 넘어가는 것
3. 이러다가 카운트가 6개가 되거나 존재하는 행렬의 마지막에 접근하면 끝

무튼 굉장히 색다르고, 추후에 다시 풀어봐야겠다는 생각이 들었다.