문제링크

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

구현방법

숫자에 중복이 가능하기 때문에 중복 조합을 통해서 값을 계산하면 되는 문제였습니다.

HashSet을 통해서 값이 중복되는 경우를 알아서 제외되도록 해주고 전부 진행되고 마지막에 hashSet의 크기를 통해서 모든 개수를 반환해줍니다.

reference : [알고리즘] 자바 순열, 중복순열, 조합, 중복조합 재귀로 구현하기 (tistory.com)

구현알고리즘

중복 조합(재귀)

CODE

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

//중복해서 같은게 가능하다.
public class Main
{
    static int[] roma= {1,5,10,50};
    static int N;
    static HashSet<Integer> roma_sum = new HashSet<>();

    static int[] checking;

    public static void main(String[] args) throws IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));


        N = Integer.parseInt(br.readLine());
        checking = new int[N];
        combi(0,0,0);

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

    private static void combi(int depth,int index,int sum) {
        //N개가 됬을경우
        if(depth == N){
            roma_sum.add(sum);
            return;
        }

        for(int idx = index; idx <roma.length;idx++){
            combi(depth+1,idx,sum+roma[idx]);
        }

    }
}