[백준] 16922. 로마 숫자 만들기 (Java)

문제

16922번: 로마 숫자 만들기

 

알고리즘

깊이우선탐색(dfs), 백트래킹

 

풀이

한 자리 당 (1, 5, 10, 50)으로 4가지의 선택지가 있다.

따라서 N이 20일 때 경우의 수는 4²⁰ = 2⁴⁰ = 2¹⁰⁴ = 약 10³⁴ = 10¹² 로 시간초과가 난다.

 

하지만 겹치는 수가 굉장히 많기 때문에 백트래킹을 이용하여 시간을 단축할 수 있다.

이를 위해 boolean형 배열 visited[N + 1][1001] 을 사용한다.

visited[i][num]은 i번 숫자를 더했을 때 합이 num이 나온 경우가 있는지를 저장한 것이다.

동일한 횟수에 동일한 합이 나온적이 있다면 앞으로 나올 결과들이 중복된 결과이므로 그 이상으로 더 진행할 필요가 없다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	static int N, answer;
	static boolean visited[][];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		N = Integer.parseInt(br.readLine());
		visited = new boolean[N + 1][1001];
		answer = 0;
		dfs(0, 0);
		System.out.println(answer);
	}

	private static void dfs(int count, int sum) {

		if (visited[count][sum]) return;
		visited[count][sum] = true;

		if (count == N) {
			answer++;
			return;
		}

		dfs(count + 1, sum + 1);
		dfs(count + 1, sum + 5);
		dfs(count + 1, sum + 10);
		dfs(count + 1, sum + 50);
	}
}