6603번 로또

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

6603번: 로또

 

문제

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

출력

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

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

 

 

---

 

풀이 방식

 

  이 문제는 주어진 수 k개의 숫자 중 6개 숫자를 뽑아야 하는 조합 문제입니다.

  조합 nCr은 서로 다른 n개의 원소 중 중복 없이 r개 원소를 선택하는 것으로, 원소의 개수가 r개인 부분집합을 구하는 것과 같습니다.

 

  조합은 r중 for문을 이용하거나 최대 깊이가 r인 재귀를 이용하여 구할 수 있는데, 코딩의 편리함을 위해 재귀를 이용하는 편이 좋습니다. 재귀 호출을 이용한 조합 생성 알고리즘은 아래와 같습니다.

 

int n; 	//총 원소의 개수
int r; 	//뽑아야할 원소의 개수
int[] input = new int[n];	//총 원소의 배열
int[] picked = new int[r];	//뽑은 원소의 배열

void combination(int cnt, int start){	//cnt:현재까지 뽑은 원소 개수, start: 조합시도할 원소 시작 인덱스
    if(cnt==r){	//r개의 원소를 뽑은 경우
    	//조합 생성 완료
        //해야할 처리하기
        return;
    }
    for(int i = start; i<n; i++){
        picked[cnt] = input[i];	//input의 i번째 원소 채택
        combination(cnt+1, i+1);	//다음 채택 고려는 input의 i+1번째부터 고려
    }
}

   

 

구현 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	static int k;
	static int[] numbers;
	static int[] picked;
	
	public static void check(int cnt, int start) {
		if(cnt == 6) {
			for(int i =0;i<6;i++) {
				System.out.print(picked[i]+" ");
			}
			System.out.println();
			return;
		}
		for(int i=start;i<k;i++) {
			picked[cnt] = numbers[i];
			check(cnt+1, i+1);
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st;
		while(true) {
			st = new StringTokenizer(br.readLine()," ");
			k=Integer.parseInt(st.nextToken());
			if(k==0) break;
			
			numbers = new int[k];
			for(int i =0;i<k;i++) {
				numbers[i] = Integer.parseInt(st.nextToken());
			}
			
			picked = new int[6];
			check(0,0);
			System.out.println();
		}
	}
}

 

 

---

 

다른 사람의 풀이

방법 1. 

=> 차이점 : dfs를 이용하여 원소 개수가 6개인 부분집합을 구했다.

https://log-laboratory.tistory.com/118

[백준] 6603번 자바 로또