[백준] 16922번 : 로마 숫자 만들기 Silver2(실버2) - JAVA[자바]

[Silver III] 로마 숫자 만들기 - 16922

문제 링크

성능 요약

메모리: 17016 KB, 시간: 156 ms

분류

백트래킹, 브루트포스 알고리즘, 조합론, 구현, 수학

제출 일자

2023년 10월 26일 11:37:00

문제 설명

로마 숫자에서는 수를 나타내기 위해서 I, V, X, L을 사용한다. 각 문자는 1, 5, 10, 50을 의미하고, 이 문제에서 다른 문자는 사용하지 않는다.

하나 또는 그 이상의 문자를 이용해서 수를 나타낼 수 있다. 문자열이 나타내는 값은, 각 문자가 의미하는 수를 모두 합한 값이다. 예를 들어, XXXV는 35, IXI는 12를 의미한다.

실제 로마 숫자에서는 문자의 순서가 중요하지만, 이 문제에서는 순서는 신경쓰지 않는다. 예를 들어, 실제 로마 숫자에서 IX는 9를 의미하지만, 이 문제에서는 11을 의미한다.

로마 숫자를 N개 사용해서 만들 수 있는 서로 다른 수의 개수를 구해보자.

입력

첫째 줄에 사용할 수 있는 문자의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 로마 숫자 N개를 사용해서 만들 수 있는 서로 다른 수의 개수를 출력한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Set;

class Main
{
    static int[] num = {1,5,10,50};
    static Set<Integer> set = new HashSet<>();
    static int n;
    
	public static void main(String args[]) throws Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        solution(0,0,0);
        bw.write(set.size() + "\n");
        bw.flush();
        bw.close();
    }
    private static void solution(int at,int depth,int sum) {
        if(depth == n){
            set.add(sum);
            return;
        }

        for(int i = at; i < 4; i++){
            solution(i,depth+1, sum + num[i]);
        }
    }
}