백준 6603번 로또 (java)

[Silver II] 로또 - 6603

문제 링크

성능 요약

메모리: 60244 KB, 시간: 292 ms

분류

백트래킹, 조합론, 수학, 재귀

제출 일자

2024년 7월 25일 22:32:06

문제 설명

독일 로또는 {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이 하나 주어진다.

출력

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

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

 

풀이

맨 처음 숫자로 총 숫자의 개수 즉 집합 S의 원소의 개수가 나오고, 이후 집합 S의 원소들이 주어진다.

집합 S에서 6개의 숫자로 부분 집합을 만들면 되는 간단한 문제다.

 

여기서 한 가지 포인트만 주의하면 된다.

 

1. 어떻게 겹치지 않도록 부분집합을 만들 것인지

 

for(int i = c;  i < N;i++) {
    if(visited[i]) {
        selected[depth] = x[i];
        visited[i] = false;
        dfs(x,i+1,depth + 1);
        visited[i] = true;
    }
}

 

필자는 다음과 같은 방식으로 중복되는 부분집합의 형성을 막았다.

 

1,2,3,4,5,6 이 선택됐다면

1,2,3,4,6,5은 선택되면 안 된다. 

 

이는 다음 dfs를 호출할 때 i=c 부분에서 c에 i+1이 들어가도록 해주면 해결할 수 있다.

 

맨 처음 i = depth로 for 문을 돌렸다가, depth는 최대 6까지밖에 못 늘어나기에,

 원소의 개수가 6개 이상이 되면 중복 제거를 할 수 없다는 사실을 깨닫고 함수에 파라미터를 추가해주었다.

 

전체 코드

public class Main{
    static int N,selected[];
    static boolean visited[];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        while(true){

            StringTokenizer st = new StringTokenizer(br.readLine());

            N = Integer.parseInt(st.nextToken());

            if(N == 0){
                break;
            }

            int x[] = new int[N];
            visited = new boolean[N];
            selected = new int[6];

            for(int  i = 0 ;i<N;i++){
                x[i] = Integer.parseInt(st.nextToken());
                visited[i] = true;
            }

            dfs(x,0,0);

            bw.write("\n");
            bw.flush();

        }

    }

    public static void dfs(int x[], int c,int depth) throws IOException {

        if(depth == 6){
            int s = Arrays.stream(selected).sum();

            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

            for (int i : selected) {
                bw.write(String.valueOf(i));
                bw.write(" ");
            }

            bw.write("\n");
            bw.flush();

            return;
        }

        for(int i = c;  i < N;i++) {
            if(visited[i]) {
                selected[depth] = x[i];
                visited[i] = false;
                dfs(x,i+1,depth + 1);
                visited[i] = true;
            }
        }
    }



}