"로마 숫자 만들기" - 16922번 S3

🎃문제설명

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

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

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

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

입력

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

출력

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

🔒제한

입력	출력
1	4
2	10
10	244

알고리즘 분류

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

🌟문제 이해 및 풀이계획

✏️처음에는 map으로 중복되는 합을 제거하고 사이즈를 통해 정답을 구하려고 했으나 시간초과가 났다.
✏️map이 너무 느린가 해서 boolean배열로 바꿨지만 별 차이는 없는 것 같았다.
✏️직접 sum으로 합만 구하지 말고 배열에 각 수를 담아서 stream으로 더해도 봤지만 stream은 오히려 더 느린 것 같았다.
✏️애초에 N이 20일 때 4^20 이면 모든 경우를 전부 해보는 방법은 불가능하다. 중복조합을 이용하여 1,0,0,0 과 0,1,0,0 0,0,1,0 0,0,0,1을 모두 같은 경우로 치고 넘어가야 한다.

✍🏻내 코드1 - 오답코드

package BOJ;

import java.util.*;

/*
 * 2021.12.01 daily algo/commit
 * 
 */

public class boj_16922 {
	
	static int[] numbers = {1,5,10,50};
//	static Map<Integer, Integer> map = new HashMap<Integer, Integer>();
	static int sum = 0;
	static int answer = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] list = new int[N];
		combination(list, numbers, 0, 0, N);
//		System.out.println(map.size());
		
		System.out.println(answer);
		sc.close();
	}
	
	static boolean[] visited = new boolean[1001];
	// depth: 현재 인덱스(0부터 시작)
	public static void combination(int[] list, int[] numbers, int depth, int cnt, int r) {
		if(cnt == r) {
//			map.put(sum, 1);
//			sum = Arrays.stream(list).sum();
			if(!visited[sum]) {
				visited[sum] = true;
				answer += 1;
			}
//			sum = 0;
			return;
		}
		for(int i=depth; i<numbers.length; i++) {
//			list[cnt] = numbers[i];
			sum += numbers[i];
			combination(list, numbers, depth, cnt+1, r);
			sum -= numbers[i];
		}
	}

}

✏️맞게 푼거 같은데 대체 왜 시간초과가 날까 생각해서 다 지우고 처음부터 다시 풀어봤다. 근데 재귀로 들어가는 과정에서 i번으로 작성해야 했는데 depth(idx)로 작성해서 같은 경우의 수도 처음부터 모두 구했기 때문에 시간초과가 났던 것이다. (즉, 4^20을 모두 했던 것... ㅠ)
✏️역시 오류에 빠졌을 때는 내가 쓴 코드에 미련을 두지 말고 전부 지우고 처음부터 다시 짜봐야 한다.

✍🏻내 코드2 - 정답코드

package BOJ;

import java.util.Arrays;
import java.util.Scanner;

/*
 * 2021.12.01 daily algo/commit
 * 
 * 중복조합
 */

public class boj_16922 {
	
	static int[] numbers = {1,5,10,50};
	static int sum = 0;
	static int answer = 0;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		int[] list = new int[N];
		combination(numbers, 0, 0, N);
		
		System.out.println(answer);
		sc.close();
	}
	
	static boolean[] visited = new boolean[1001];
	// idx: 현재 인덱스(0부터 시작)
	public static void combination(int[] numbers, int idx, int cnt, int r) {
		if(cnt == r) {
			if(!visited[sum]) {
				visited[sum] = true;
				answer += 1;
			}
			return;
		}
		for(int i=idx; i<numbers.length; i++) {
			sum += numbers[i];
			combination(numbers, i, cnt+1, r);
			sum -= numbers[i];
		}
	}
}

강의내용

✔️모든 경우의 수는 4^N가지
✔️하지만, 순서가 다르고 개수가 같은 것은 같은걸로 치기 때문에 경우의 수는 N^4가지라고 할 수 있다.
✔️1,5,10의 개수를 알면 나머지 하나인 50의 개수도 알 수 있기 때문에 N^3가지가 나온다.
✔️따라서 3중 for문을 이용하여 각각의 로마 숫자의 개수를 파악하고 합을 구하여 경우의 수를 구할 수 있다.

✍🏻내 코드3 + 강의

package BOJ;

import java.util.Scanner;

/*
 * 2021.12.01 daily algo/commit
 * 
 * Brute Force
 * 각각의 1,5,10,50을 사용한 개수만 파악하면 된다. 
 * 넷중 세개의 개수만 알면 나머지 하나도 알 수 있으므로 3중 for문을 이용하여 간단하게 풀이 가능하다.
 */

public class boj_16922_2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt();
		boolean[] visited = new boolean[1001];
		
		int answer = 0;
		for(int i=0; i<=N; i++) {
			for(int j=0; j<=N-i; j++) {
				for(int k=0; k<=N-i-j; k++) {
					int l = N-i-j-k;
					int sum = i+j*5+k*10+l*50;
					if(!visited[sum]) {
						visited[sum] = true;
						answer += 1;
					}
				}
			}
		}
		System.out.println(answer);
		sc.close();
	}

}