[B0J]로또(6603)

티어 : Sliver 2
정답여부 : 오답
알고리즘 유형 : 수학,조합론,백트래킹,재귀
시간 제한 : 1초

💡문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

💡입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다. 

💡출력

각 테스트 케이스마다 수를 고르는 모든 방법을 출력한다. 이때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

💡예제 입력1

7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

💡예제 출력1

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7

1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

💡문제 분석 요약

• 주어진 숫자에 모든 숫자를 입력할 경우의 수를 구하면 되는 문제

💡알고리즘 설계

• K : 입력받는 숫자
• lotto : 경우의 수를 나타낼 수의 배열

1. 각 수를 입력 받고 DFS를 호출
2. DFS 함수 내부 코드 동작 설명

private static void DFS(int depth, int start) {
    if(depth == 6) {
        for(int i = 0; i < K; i++) {
            if(visit[i]) {
                System.out.print(lotto[i] + " ");
            }
        }
        System.out.println();
        return;
    }
    for (int i = start; i < K; i++) {
        visit[i] = true; // 방문 체크
        DFS(depth + 1, i + 1); // 재귀호출, 하나의 깊이를 탐색 
        visit[i] = false; // 초기화
    }
}

1. depth가 6이면 현재 선택된 6개의 숫자를 출력
   • 예제 동작 과정
     1. DFS(0, 0)
     2. 호출.첫 번째 숫자로 1 선택,
     3. DFS(1, 1) 호출.두 번째 숫자로 2 선택,
     4. DFS(2, 2) 호출.세 번째 숫자로 3 선택,
     5. DFS(3, 3) 호출.네 번째 숫자로 4 선택,
     6. DFS(4, 4) 호출.다섯 번째 숫자로 5 선택,
     7. DFS(5, 5) 호출.여섯 번째 숫자로 6 선택,
     8. DFS(6, 6) 호출.depth가 6이므로 1 2 3 4 5 6 출력.
     9. 6 선택 취소, 다음 숫자 7 선택, DFS(6, 7) 호출.
     10. depth가 6이므로 1 2 3 4 5 7 출력.
   • 입력이 7 1 2 3 4 5 6 7인 경우, 아래와 같이 동작
2. 그렇지 않으면, start부터 K까지 반복하면서 숫자를 선택하고(visit[i] = true), 재귀를 호출
3. 재귀 호출이 끝나면 선택을 취소하고(visit[i] = false), 다음 숫자를 선택

💡시간복잡도

• O(N)

💡코드

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static boolean[] visit;
    static int[] lotto;
    static int K;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            if (K == 0) break;
            lotto = new int[K];
            visit = new boolean[K];
            for(int i = 0; i < K; i++) {
                lotto[i] = Integer.parseInt(st.nextToken());
            }
            DFS(0, 0);
            System.out.println(); // 각 테스트 케이스 사이에 빈 줄 출력
        }
    }

    private static void DFS(int depth, int start) {
        if(depth == 6) {
            for(int i = 0; i < K; i++) {
                if(visit[i]) {
                    System.out.print(lotto[i] + " ");
                }
            }
            System.out.println();
            return;
        }
        for (int i = start; i < K; i++) {
            visit[i] = true; // 방문 체크
            DFS(depth + 1, i + 1); // 재귀호출, 하나의 깊이를 탐색 
            visit[i] = false; // 초기화
        }
    }
}

💡 틀린 이유

백트래킹을 사용하는 방법을 잘 몰랐던 점.

입력 부분에서 7과 로또 번호를 따로 입력 받아줘야 하는지..

다른 구현 방법이 있는지는 모르겠다.. 대신 visit 없이 재귀를 구현하는 코드도 있어서 가져왔다.

💡 틀린 부분 수정 or 다른 풀이

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();
    static int[] lotto;
    static int K;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            K = Integer.parseInt(st.nextToken());
            if (K == 0) break;
            lotto = new int[K];
            for(int i = 0; i < K; i++) {
                lotto[i] = Integer.parseInt(st.nextToken());
            }
            generateCombinations(new ArrayList<>(), 0);
            System.out.println(); // 각 테스트 케이스 사이에 빈 줄 출력
        }
    }

    private static void generateCombinations(List<Integer> combination, int start) {
        if(combination.size() == 6) {
            for(int num : combination) {
                System.out.print(num + " ");
            }
            System.out.println();
            return;
        }
        for (int i = start; i < K; i++) {
            combination.add(lotto[i]);
            generateCombinations(combination, i + 1);
            combination.remove(combination.size() - 1); // 마지막 요소 제거
        }
    }
}

 

💡 느낀점 or 기억할정보

생각보다 좀 까다롭고 어렵다고 느꼈다. DFS로 구현해야겠는데 방법이 생각이 안 나서 조금 까다로운 문제인거 같았다.