[백준_16922번] 로마 숫자 만들기

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)이 주어진다.

 

[코드]

import java.util.*;

public class BaekJoon_16922 {
	static StringBuilder sb=new StringBuilder();
	static int[] visited=new int[10001]; // 수의 합의 중복을 체크하는 배열
	static int n,answer=0;
	static int[] arr= {1,5,10,50};
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		
		dfs(0,0,0);
		sb.append(answer);
		
		System.out.println(sb);
	}
	static void dfs(int depth, int start, int sum) {
		if(depth==n) {
			// 수의 합이 이전에 나온적 없는 수라면 count
			if(visited[sum]==0) {
				answer++;
				visited[sum]=1;
			}
			return;
		}
		
		// 수의 선택의 중복을 피하기 위해 start 부터 탐색 시작
		for(int i=start;i<4;i++) {
			dfs(depth+1,i,sum+arr[i]);
		}
	}
}

 

[고찰]

 이번 문제는 백트래킹을 이용하여 풀 수 있다. 이전에 풀었던 백트래킹 기본 예제인 N과 M 시리즈와 굉장히 비슷한 문제로 1, 5, 15, 20 이 4개의 숫자중 n개를 선택하여 더해 만들 수 있는 숫자의 개수를 구하는 문제이다. 처음에는 결과의 중복을 확인하기 없애기 HashSet을 사용하여 풀었는데 시간초과를 받아 대체로 boolean 배열을 사용하였다. 시간초과만 주의한다면 쉽게 해결할 수 있는 문제였다.