[백준BOJ] 6603번 로또.java

 

백준 저지에서 로또를 자바를통해 풀어 보았다. 

 

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

6603번: 로또

6603번 로또.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

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개를 뽑는 모든 경우를 출력하는 문제이다. 로또 번호의 순서는 중요하지 않기 때문에 조합문제이다. 단 주어진 배열에 대해 index로 접근해야 해당 숫자를 출력할 수 있다.

 

일반적인 조합과 같은 알고리즘을 사용하면 된다. 단 조합을 통해 뽑는 숫자들이 배열의 index라는 것을 기억해야한다. 6개의 숫자를 뽑기 때문에 뽑은 숫자가 6개가 되면 index로 접근하여 선택한 로또 번호들을 출력한다.

코드

//6603번 로또.java
package week5;

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

public class 로또_6603 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    
    static int N;
    static int[] lotto;
    static int[] select;
    public static void main(String[] args) throws NumberFormatException, IOException {
		while(true) {
			st = new StringTokenizer(br.readLine()," ");
			N = Integer.parseInt(st.nextToken());
			if(N==0)break;
			
			lotto = new int[N];
			select = new int[6];
			for(int i=0;i<N;i++) {
				lotto[i] = Integer.parseInt(st.nextToken());
			}
			com(0,0);
			sb.append("\n");
		}

		System.out.println(sb.toString());
	}
    
    public static void com(int cnt, int start) {
    	if(cnt==6) {
    		for(int i=0;i<6;i++) {
    			sb.append(lotto[select[i]]+" ");
    		}sb.append("\n");
    		return;
    	}
    	for(int i=start;i<N;i++) {
    		select[cnt]=i;
    		com(cnt+1,i+1);
    	}
    }
}