[BOJ_6603 | recursive] 로또

로또 문제는 n개에서 m개를 선택하는 경우의 수를 나열하는

선택 알고리즘 문제의 일종이었던 것 같다.

Lotto라는 함수를 만들어서 

Divde and Conquer 방법으로 문제를 해결하는 쪽을 선택했다.

재귀 함수를 이용하였으며

Lotto 라는 함수는 번호가 담겨있는 배열의 포인터와, 번호를 몇개 선택했는지를 알려주는 카운터, 

배열의 번호 정보가 담긴 인덱스,

그리고 주어진 로또번호의 개수, 그리고 리턴해야 할 스트링을 파라미터로 전달받는다.

재귀함수가 한번 호출될 때마다 번호가 하나씩 선택되며, 카운터가 증가하고 

다음에 선택해야 할 번호의 개수가 줄어드는 식이다

예를 들면

1, 2, 3, 4, 5, 6, 7 이 7개의 번호가 주어졌을 때

첫번째 함수에서는

1이 선택되거나 2가 선택되고 (3부터 선택하게 되면 6개를 선택할 수 없다.)

1과 2가 또 각각 로또 함수를 호출해서

1 함수는 2 또는 3을 호출하고

2함수는 3을 호출하고....

이렇게 DFS방법으로 문제를 쪼개니 문제가 해결되었다.

import java.util.*;
 
public class BOJ_6603 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
 
        while(true){
            int n = input.nextInt();
            if(n==0) break;
            int[] arr = new int[n];
            for(int i=0;i<n;i++){arr[i] = input.nextInt();}
            String retStr = "";
            for(int i=0;i<n-5;i++){
                Lotto(arr, 0, i, n, retStr);
            }
            System.out.println();
        }
    }
    public static void Lotto(int[] arr, int cnt, int index, int n, String retStr){
        cnt++;
        if(cnt==7){
            System.out.println(retStr);
            return;
        }else{
            retStr += arr[index]+" ";
            if(cnt<6) {
                for (int i = index + 1; i <= n - (6 - cnt); i++) {
                    Lotto(arr, cnt, i, n, retStr);
                }
            } else Lotto(arr, cnt, 0, n, retStr);
        }
    }
}