백준 16922 로마 숫자 만들기 (JAVA 자바)

문제 출처 - https://www.acmicpc.net/problem/16922

16922번: 로마 숫자 만들기

 

문제

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

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

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

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

 

 

입력

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

 

 

출력

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

 

문제 유형

중복 조합

 

코드

import java.util.Scanner;

public class BJ16922_로마숫자만들기 {
	static int N;
	static int num[];
	static int sum[];
	static int res;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		num = new int []{1, 5, 10, 50};
		sum = new int [10000];
		pick(0, 0, 0);
		System.out.println(res);
	}
	
	static void pick(int cnt, int idx, int s) {
		if(cnt == N) {
			if(sum[s] == 0) {
				sum[s] = 1;
				res++;
			}
			return;
		}
	
		for (int i = idx; i < 4; i++) {
			pick(cnt + 1, i, s + num[i]);
		}
	}
}

 

문제 풀이

중복 조합 문제이다. 수끼리 더해주는 것으로 순서와는 상관 없기 때문에 (1 + 5와 5 + 1은 같다. 교환법칙이 성립하기 때문이다.) 조합 문제인데 이제 1, 5, 10, 50 을 중복 조합할 수 있기 때문에 중복 조합 문제가 된다. 

처음에는 sum 배열을 사용하여서 이미 나온 수인지 체크를 해주지 않았었는데, 그러니까 3번 테케에서 286인가가 나온다. 244가 답이 되어야 하는데 말이다. 따라서 이미 나온 수인지 체크를 해주는 sum 배열을 만들었다. int 배열로 만들었는데 지금 생각해보니 boolean 자료형의 배열로 만드는 것이 메모리를 절약할 수 있고 더 나은 방법 같다.