[백준] 16922 로마 숫자 만들기 - Backtracking / Java

• 문제 링크

16922번: 로마 숫자 만들기

 

• 풀이 과정

4개의 수 중에서 n개의 순열을 찾되, 서로 다른 수를 찾아야 하는 문제의 조건을 고려하여야 한다.

 

예를 들어 n = 6 일 때, I I I I I L = 1 + 1+ 1+ 1+ 1 + 50 = 55,

V X X X X X = 5 + 10 + 10 + 10 + 10 + 10 = 55 과 같이 합이 중복인 값이 존재한다.

따라서 1 ≤ N ≤ 20 조건에 의해 합의 최대 값은 50 * 20 = 1000,

인덱스의 범위를 벗어나지 않기 위해 크기가 1001 인 boolean 배열을 생성하여 중복을 검사한다.

 

백트래킹을 활용하여 순열의 합이 구해질 때마다 해당 배열에 방문 처리를 하여 중복을 제거하며

이러한 조건에 의해 구해진 합의 개수 cnt 를 정답으로써 출력한다.

 

• 풀이 코드

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

public class Main {

	static int n, cnt;
	static int[] num = { 1, 5, 10, 50 };
	static boolean[] visit = new boolean[1001];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		n = Integer.parseInt(br.readLine());

		recur(0, 0, 0);

		bw.write(cnt + "\n");
		bw.flush();
	}

	private static void recur(int idx, int sum, int depth) {
		if (depth == n) {
			if (!visit[sum]) {
				visit[sum] = true;
				cnt++;
			}

			return;
		}

		for (int i = idx; i < 4; i++)
			recur(i, sum + num[i], depth + 1);
	}

}