[백준] 6603번 로또

1) 생각

오름차순으로 숫자 배열이 주어지면 오름차순으로 6가지 숫자를 조합할 수 있는 경우를 만들어라. 

우선 입력으로 주어지는 k의 값이 7~12 이므로 완전탐색을 통해 충분히 문제를 해결할 수 있으며, 반복문으로 나타내려면 어렵지만 재귀로 구현하면 쉽게 구현 할 수 있는 문제다. 오름차순으로 출력을 해야한다는 조건이 있지만 이미 오름차순으로 입력이 주어지기때문에 재귀를 통해 DFS 탐색을하면 자동으로 순서대로 출력이된다.

2) 방안

재귀를 통해 탐색을 하면서 자신을 포함할 때와 그렇지 않을 때를 넘겨준다. 끝낼 조건을 위해 Count 변수인 cnt가 6이 되었을 때, 그리고 계속 나아가는것을 막기위해 인덱스를 나타내는 idx 값이 주어진 수 k와 같아질 경우 return을 하도록 하였다.

처음에 solve Method의 매개변수 값으로 ""을 넣어주고 있기 때문에 모든 값의 맨 처음이 " "로 시작하게된다 따라서 맨 앞의 공백을 제거하여 출력하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main{
    static int[] arr;
    static int n;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            k = Integer.parseInt(st.nextToken());
            if(k==0) break;
            arr = new int[k];
            for(int i=0;i<k;i++)
                arr[i] = Integer.parseInt(st.nextToken());
            
            solve(0,"",0);
            System.out.println();
        }
    }
    
    private static void solve(int cnt,String t,int idx) {
        if(cnt==6) {
            System.out.println(t.substring(1));
            return;
        }else if(cnt>6) return;
        else if(idx==k) return;
        
        solve(cnt+1,t+" "+arr[idx],idx+1);
        solve(cnt,t,idx+1);
    }
}