백준 16922번 - 로마 숫자 만들기

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

16922번: 로마 숫자 만들기

 

 

 

 

로마 숫자 I, V, X, L 4개 중에서 중복해서 N개를 뽑는 중복 조합 문제이다.

 

중복 조합을 돌려서 조합의 결과 배열에 로마 숫자들의 값을 담도록 했다.

그리고 조합이 완성되면 그 합을 계산해, 새로운 값이면(숫자이면) 리스트에 담도록 했다.

그러면 정답은 리스트의 사이즈로 도출하면 된다.

 

 

 

 

 

코드

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
	static int N;
	static int[] romeNum = {1, 5, 10, 50};
	static int[] result;
	static List<Integer> list;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		N = sc.nextInt();
		
		result = new int[N];
		list = new ArrayList<>();

		comb(0, 0);
		
		System.out.println(list.size());
	}

	public static void comb(int start, int depth) {
		if(depth == N) {
			int sum = 0;
			for(int n : result) {
				sum += n;
			}
			
			if(!list.contains(sum)) {
				list.add(sum);
			}
			
			return;
		}
		
		for(int i = start; i < romeNum.length; i++) {
			result[depth] = romeNum[i];
			comb(i, depth + 1);
		}
	}
}

 

 

 

 

 

 

결과