[백준 16922] 로마 숫자 만들기 (Java) - DFS, 백트래킹

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

로마 숫자 만들기

문제

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

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

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

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

입력

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

출력

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

예제 입력 1 복사

1

예제 출력 1 복사

4

I, V, X, L을 만들 수 있다.

예제 입력 2 복사

2

예제 출력 2 복사

10

2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다.

예제 입력 3 복사

10

예제 출력 3 복사

244

---

풀이

package silver;

import java.util.Scanner;

public class Main {
    static int N;
    static int[] romes = {1, 5, 10, 50};
    static boolean[][] visited;
    static boolean[] possible;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        visited = new boolean[N+1][N*50+1];
        possible = new boolean[N*50+1];

        DFS(0,0);

        int count = 0;
        for (boolean b : possible){
            if (b) count++;
        }

        System.out.println(count);
    }
    private static void DFS(int depth, int sum) {
        if (depth == N) {
            possible[sum] = true;
            return;
        }

        if (visited[depth][sum]) return; // 이미 기록된 값이면 종료

        visited[depth][sum] = true; // 로마숫자 depth개 사용해서 만든 sum

        for (int r : romes){
            DFS(depth+1, sum + r);
        }
    }
}

• DFS 를 활용한 문제
• visited[depth][sum]: 중복된 (깊이, 합) 경로를 막아줌 → 시간 단축
• possible[sum]: 만들 수 있는 합을 저장
• 마지막에 possible 배열을 순회하면서 true인 개수만 세면 정답