[ 완전탐색 ] 6603번 로또

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

6603번: 로또

---

문제

 

---

해결 방법

 

순열 문제라고 생각했습니다. 

기본적으로 k개의 수 중 6개의 수를 골라야 하며, 수는 사전순으로(오름차순) 배치를 해야 하기에

범위를 나눠 생각했습니다.

 

k개의 수 중 첫번째 자리에 올 수 있는 수는 (k-6)+1 가지 입니다.

예를 들어, k가 7이라면 첫번째로 올 수 있는 수는 1과 2 입니다.

3이 되는 순간 3, 4, 5, 6, 7 이 다섯 가지의 수밖에 없기 때문입니다. 

그렇기에 첫번째 올 수 있는 수를 한정해 두었습니다.

 

그 다음으로 올 수 있는 수들을 정하는 방법을 DFS로 선택하였습니다.

BFS가 안되는 이유는 모든 출력이 사전순으로 배치되어야 하기 때문입니다.

boolean 배열을 만들어 각 수들이 포함되는지 안되는지를 체크해두고

체크된 수의 개수를 cnt 변수에 기록하여 cnt가 6이 되는 순간 출력을 하는 dfs 함수를 만들었습니다.

 

---

코드

 

import java.io.*;
import java.util.*;

class Main {
    static void dfs(int i, int[] lotto, boolean[] flag, int cnt) {
        int k = lotto.length;
        if(cnt == 6) {
            for(int j=0; j<k; j++) {
                if(flag[j]) System.out.print(lotto[j] + " ");
            }
            System.out.println();
        } // 출력
        else {
            for(int j=i+1; j<k; j++) {
                flag[j] = true;
                cnt++;
                dfs(j, lotto, flag, cnt);
                flag[j] = false;
                cnt--;
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());
            if(k==0) break; // 0이 입력되면 종료
            int[] lotto = new int[k];
            for (int i = 0; i < k; i++) lotto[i] = Integer.parseInt(st.nextToken());
            for(int i=0; i<=k-6; i++) {
                boolean[] flag = new boolean[k];
                flag[i] = true;
                int cnt = 1;
                dfs(i, lotto, flag, cnt);
            }
            System.out.println();
        }
    }
}