백준 6603번 로또

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

완전탐색 문제이다.

k개의 수 중 6개를 고르는 모든 경우를 출력하는 문제였다.

아직 재귀를 이용한 완전탐색이 익숙치 않아 종만북도 다시보고 더듬더듬거리며 풀었다.

1. 우선 k를 입력 받고 k크기의 배열 s를 만들어 수들을 입력받았다.

2. 재귀함수로 0부터 k-1까지 수 중에 6개를 선택하여 ArrayList에 추가해주었다.

3. 재귀호출중에 6개를 모두 선택한 경우에는 ArrayList에 있는 값을 s배열에 인덱스로 넣어주어 출력했다.

재귀함수를 통해 집합 s의 값을 바로 선택하는 것이 아닌, 0~k-1의 수 중에서 6개를 선택하여 마지막 출력을 할때 배열 s의 인덱스로 넣어 출력하도록했는데

그 이유는 재귀호출중에 골라야 할 값들 중 최소값을 구할때 편하게 구하기 위해서 였다.

만약 집합의 값을 바로 고르는 방법을 택했다면

골라야 할 값들 중 최소값을 구할때, 제일 마지막으로 고른 값을 다시 집합에서 찾고 그 다음값을 찾아줘야하는데

그에 반해 연속된 0~k-1의 수 중에서 골라야 할 값들 중 최소값을 구하기 위해서는 마지막에 고른 값에 1만 더해주면 되기 때문이다.

뭐 아무튼 아래는 소스코드이다.

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    static int k;
    static int[] s;
    static ArrayList<Integer> ar = new ArrayList<Integer>();
    
    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];
            for(int i=0; i<k; i++) {
                s[i] = sc.nextInt();
            }
            pick(6);
            System.out.println();
        }
    }
    
    static public void pick(int toPick) {
        if(toPick == 0) {
            printPicked();
        }
        
        int smallest = ar.isEmpty() ? 0 : ar.get(ar.size()-1) + 1;
        
        for(int next = smallest; next < k; next++) {
            ar.add(next);
            pick(toPick - 1);
            ar.remove(ar.size()-1);
        }
    }
    
    static public void printPicked() {
        for(int i=0; i<ar.size(); i++) {
            System.out.print(s[ar.get(i)] + " ");
        }
        System.out.println();
    }
}