로마 숫자 만들기 16922

https://www.acmicpc.net/problem/16922

이전에 사용되었던 조합이 사용되지 않도록 하는 int start 코드를 사용했어도 합계가 동일한 상황도 있다. 전혀다른 원소들의 조합으로도 같은 합계가 나올 수 있다. 예를들어 10을 입력 받았을때 합계가 46인 경우가 2가지 나왔다 그래서 HashSet 을 사용해서 해결하였다.

import java.io.*;
import java.util.*;

public class Main
{
    static BufferedReader br;
    static int N;

    static int[] arr;

    static int[] num = {1, 5, 10, 50};

    static Set<Integer> set = new HashSet<>();
    public static void main(String[] args) throws IOException
    {
        inputProcess();

        search(0, 0);

        System.out.println(set.size());
    }

    public static void inputProcess() throws IOException
    {
        br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        arr = new int[N];
    }

    public static void search(int depth, int start)
    {
        if(depth == N)
        {

            int sum = 0;
            for(int i = 0; i < depth; ++i)
            {
                sum += arr[i];
            }

            set.add(sum);

            return;
        }

        for(int i = start; i < num.length; ++i)
        {
            arr[depth] = num[i];
            search(depth+1, i);
        }
    }
}