6603_로또 (JAVA)

6603번: 로또

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static StringBuilder sb = new StringBuilder();

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		while(true){
			st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken());
			if(n==0)
				break;

			int[] num = new int[n];
			int[] temp = new int[6];
			for(int i=0; i<n; i++){
				num[i] = Integer.parseInt(st.nextToken());
			}

			choose(num, temp, 0, 0);
			sb.append('\n');
		}
		System.out.print(sb);
		br.close();
	}

	private static void choose(int[] num, int[] temp, int num_idx, int temp_idx){
		if(temp_idx == 6){
			String str = "";
			for(int i=0; i<temp.length; i++){
				str += temp[i]+" ";
			}
			sb.append(str).append('\n');
			return;
		}
		if(num_idx >= num.length)
			return;

		temp[temp_idx] = num[num_idx];
		choose(num, temp, num_idx+1, temp_idx+1);
		choose(num, temp, num_idx+1, temp_idx);
	}
}

 

주어진 n개의 수 중에서 6개를 중복없이(자기 자신을 포함하지 않고), 순서 상관없이 뽑는 문제이다.

총 가짓수를 nC6으로 표현할 수 있고, 조합으로 구현했다.

 

 

 

** 조합 참고

조합 nCr