백준 16922 java : 구현, DFS, 재귀

왜 재귀 DFS를 사용했는가?

순서가 상관없는 문자들의 조합을 구해야 한다. 문자 각각에 값이 지정돼 있으니, 문자열을 따로 만들지는 않는다. 조합, 즉 순열을 구하기 위해 주로 재귀 DFS가 사용된다. 재귀방식은 스택방식보다 구현이 쉽지만, 효율이 상대적으로 떨어진다. N의 최댓값이 20이고, 다음 단계가 4개 가짓수 밖에 안되기에 재귀로도 충분하다고 생각한다.
sum값을 set 자료구조에 삽입하면 총계값이 같은 경우 중복제거를 해준다.

import java.util.*;

public class bj16922 {
    static Scanner sc = new Scanner(System.in);
    static Set<Integer> numbers = new HashSet<>();
    static int []values = {1, 5, 10, 50};
    static int N;

    public static void main(String[] args) {
        N = sc.nextInt();

        System.out.println(findAnswer());

        sc.close();
    }

    public static int findAnswer() {
        int i;
        //N = 2일 때
        // II, IV, IX, IL, VV, VX, VL, XX, XL, LL -> 10개

        //N = 3일 때?
        // III, IIV, IIX, IIL, IVV, IVX, IVL, IXX, IXL, ILL, ....
        // -> 조합, 순서 상관없이 중복을 허용하지 않는 조합을 구해야 함

        DFS(0, 0, 0);

        return numbers.size();
    }

    public static void DFS(int count, int start, int sum) {
        if(count == N){
            System.out.println(sum);
            numbers.add(sum);
            return;
        }

        for(int i = start; i < values.length; i++){
            DFS(count + 1, i, sum + values[i]);
        }
    }
}