[백준 6603 - Java] 로또

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이 하나 주어진다. 

출력

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

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

 

풀이

 

이 문제는 이미 오름차순으로 집합 S가 주어질 정도로 친절한 문제입니다.

저는 재귀함수를 호출하면서 숫자를 하나씩 추가하고 6개를 모두 추가한 후에는 출력하고 반환해주고, 6개가 모두 추가되기 전에 집합 S의 수들을 모두 확인했다면 바로 반환해주는 방식으로 구현했습니다.

 

import java.util.Scanner;

public class Main {

	static int K;
	static int[] S;
	static int[] nums;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		while(true) {
			K = sc.nextInt();
			if(K == 0)
				break;
			S = new int[K];
			nums = new int[6];

			for(int i=0; i<K; i++)
				S[i] = sc.nextInt();

			pickNum(0, 0);
			System.out.println();
		}

	}

	static void pickNum(int idx, int cnt) {
		if(cnt == 6) {
			for(int i=0; i<6; i++)
				System.out.print(nums[i]+" ");
			System.out.println();
			return;
		}
		
		if(idx == K)
			return;
		
		for(int i=idx; i<K; i++) {
			nums[cnt] = S[i];
			pickNum(i+1, cnt+1);
		}
	}

}