[Java] 백준 16922 : 로마 숫자 만들기

🔗 문제 내용

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

16922번: 로마 숫자 만들기

 

🌱 문제 풀이 방법

중복 조합을 이용해서 풀었음.

처음에는 경우의 수만 구해서 풀려고 했지만, 수가 같은 경우도 있어서 원하는 결과가 나오지 않았음.

 

🤔 공부가 필요한 부분

순조부(순열, 조합, 부분집합) 점점 잊고있는데 리마인드가 필요함!

 

💻 코드

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

public class Main {

    static int N;
    static int [] arr = new int[]{1,5,10,50};
    static HashMap<Integer, Integer> map = new HashMap<>();

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        combination(0,0,0);
        System.out.println(map.size());
    }

    public static void combination(int sum, int idx, int cnt){
        if(cnt == N){
            if(!map.containsKey(sum)){
                map.put(sum,0);
            }
            return;
        }

        for(int i=idx;i<4;i++){
            sum+=arr[i];
            combination(sum,i,cnt+1);
        }
    }
    }