👩‍💻 BOJ_6603_로또

💬 결과의 위치와는 상관 없이 6개 자리를 뽑는 것이기 때문에 조합 을 이용해 해결하였습니다. 그 중에서 재귀 방식을 사용했습니다. 순열/조합은 알고리즘 자체를 암기해야겠습니다.

📄 문제

독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다.

수를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

💡 풀이 방법

• 1, 2, 3, 4, 5, 6, 7 숫자가 있을 때 각 숫자를 뽑을 경우, 뽑지 않았을 경우를 더해 모든 방법을 구한다.

🔥 코드

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

public class 로또 {
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int n = Integer.parseInt(st.nextToken()); 
			int arr[] = new int[n+1];
			int visit[] = new int[n+1];
			
			if(n == 0) {
				break;
			}
			
			// 배열 저장
			for(int i = 1; i < n + 1; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
		
			// 조합 start! 
			com(arr, visit, 1, 6);
			System.out.println();
		}
		
		
	}
	
	static void com(int arr[], int visit[], int depth, int r) {
		if(r == 0) {
			for(int i = 1; i < arr.length; i++) {
				if(visit[i] == 1) {
					System.out.print(arr[i] + " ");
				}
			}
			System.out.println();
			return; 
		}
		if(depth == arr.length) {
			return;
		}
		else {
            visit[depth] = 1;
            com(arr, visit, depth + 1, r - 1);
 
            visit[depth] = 0;
            com(arr, visit, depth + 1, r);
        }
		
	}
}