#6305. 로또

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

1. 문제 이해

 n(6 < n < 13)개 중에 6개를 뽑아 로또번호를 완성하는 것이 목표 입니다.

전형적인 완전 탐색 문제입니다.

2. 접근 방법

 dfs를 사용하여 문제를 해결해 보겠습니다. 

초기 깊이는 0부터 시작하며, 깊이가 6이 되었을때 방문했던 기록을 이용하여 6개의 숫자를 출력합니다.

탈출조건은 n개를 모두 탐색했을때로 두겠습니다.

인덱스 (0 ~ n-1) 에는 숫자가 들어 있고 n을 가르켰을때는 없으므로 루프 탈출!!

한가지 더!! 출력하는 것이 먼저!! 그 다음이 탈출 조건이 오도록 코드를 짜야 한다!!

3. 문제 해결

#include <cstdio>
#include <string.h>
#define MAX_SIZE 14
using namespace std;
 
int n;
int lotto[MAX_SIZE];
bool visit[MAX_SIZE];
 
void dfs(int cur, int cnt) {
    if (cnt == 6) {
        for (int i = 0; i < n; i++) {
            if (visit[i]) printf("%d ", lotto[i]);
        }
        printf("\n");
    }
    if (cur == n) return;
 
    visit[cur] = 1;
    dfs(cur + 1, cnt + 1);
    visit[cur] = 0;
    dfs(cur + 1, cnt);
}
 
int main() {
 
    while (true) {
        scanf("%d", &n);
        if (n == 0) break;
        for (int i = 0; i < n; i++) {
            scanf("%d", &lotto[i]);
        }
        memset(visit, false, sizeof(visit));
        dfs(0, 0);
        printf("\n");
    }    
 
    return 0;
}

※ dfs로 문제를 접근할때 

  1) 깊이를 무엇으로 정할지,

  2) 탈출조건을 무엇으로 정할지 에 유의하며 문제를 하도록 해야겠다!