[BOJ - JAVA] 16922 - 로마 숫자 만들기(DP, 조합)

# 주소

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

16922번: 로마 숫자 만들기

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.Scanner;

public class Main {
	static int N;
	static int num[];
	static int sum[];
	static int res;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		num = new int []{1, 5, 10, 50};
		sum = new int [10000];
		dfs(0, 0, 0);
		System.out.println(res);
		scan.close();
	}
	
	static void dfs(int index, int idx, int s) {
		if(index == N) {
			if(sum[s] == 0) {
				sum[s] = 1;
				res++;
			}
			return;
		}
	
		for (int i = idx; i < 4; i++) {
			dfs(index + 1, i, s + num[i]);
		}
	}
}

위에 풀이로 푸셔도 되고 밑에 코드로 푸셔도 됩니다. 다만 아래의 코드는 HashSet을 이용하여 푼 문제라 n값이 커지니까 시간이 조금 걸리고 시간 초과가 나네요.

사실 이 문제는 n이 4일 때 까지는 중복조합 문제입니다. 왜냐하면 n이 4일 때 까지는 (서로 겹치는 것이 없으므로) 1의 개수 4개, 5의 개수 4개, 10의 개수 4개, 50의 개수 4개에서 아무거나 4개를 중복을 허용하여 뽑는 것과 같은 메커니즘이기 때문입니다. 하지만 문제에서 입력 방식이 n은 20까지이고 n이 5가 되면서 겹치는 부분(예를 들면 1이 5개인 것과 5가 1개 있는 것과 같은)이 생기기 때문에 손코딩이 조금 필요합니다.

백준에 제출해서 정답을 맞추려면 위의 코드로 입력하셔야 합니다. 위의 코드에서는 백트래킹 방식으로 풀었습니다.

그리고 미리 num이라는 배열에 1,5,10,50이라는 데이터를 저장하고 선택되는 num배열의 값에 따라 sum에 다 더해줍니다.

다만 sum의 인덱스가 기존에 저장되어 있다면(-> sum 인덱스가 곧 n개의 배열을 더한 값입니다.) 시행하지 않고, sum의 인덱스가 기존에 없을 때에만(sum[s] == 0 일 때만) res를 증가시켜서 res를 출력하면 원하는 정답을 얻으실 수 있겠습니다.

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    static int n;
	static int sum;
	static int[] arr;
	static ArrayList<Integer> list;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		arr = new int[4];
		arr[0] = 1; arr[1] = 5; arr[2] = 10; arr[3] = 50;
		list = new ArrayList<Integer>();

		dfs(0,0);
		HashSet<Integer> hashSet = new HashSet<Integer>(list);
		ArrayList<Integer> resultList = new ArrayList<Integer>(hashSet);

		System.out.println(resultList.size());
		scan.close();
	}
	public static void dfs(int index, int sum) {
		if(index == n) {
			list.add(sum);
			return;
		}

		for(int i = 0; i < 4; i++) {
			dfs(index + 1, sum + arr[i]);
		}
	}
}

이 코드에서는 HashSet이라는 자료구조를 사용했습니다. HashSet은 기본적으로 자료 타입을 미리 설정해주고 가는 것이 좋은데요. 우리는 Integer타입을 다루기 때문에 정수형으로 선언합니다. 

그리고 각 arr에 1,5,10,50의 데이터를 넣고 Integer타입의 ArrayList를 먼저 선언합니다.(속도가 빠르기 때문)

그리고 이것도 똑같은 방식으로 백트래킹을 이용합니다.

합해진 sum마다 list에 전부 삽입을 하고 이를 HashSet에 넣습니다.

기본적으로 HashSet에 데이터가 들어가게 되면 중복값은 입력이 되지 않습니다. 그렇기 때문에 때로는 편하게 코딩을 하고싶으면 이런 자료구조를 이용하면 상당히 편리하겠죠??

이후 ArrayList를 resultList라는 이름으로 다시 선언해주는데 아까 list를 넣었던 hashSet을 넣습니다. 

최종적으로 list의 크기를 출력하면 되므로 resultList.size()를 입력하면 중복되지 않고 저장된 배열의 크기를 알 수 있습니다.

감사합니다.