[백준 Baekjoon] 16992번 로마 숫자 만들기 - JAVA

백준 Baekjoon 16992번 로마 숫자 만들기 - JAVA

---

문제 풀이

4가지의 로마 숫자를 활용하여 만들어 낼 수 있는 수의 개수를 찾는 문제이다. 같은 숫자를 여러번 사용가능한 중복 조합의 문제이다. 순서는 신경쓰지 않아 백트래킹의 반복문에서 i번 부터 for문을 시작하면 된다.

주의할 점은 이 문제에서는 로마 숫자로 만든 수를 찾는 문제로 51 (50 + 1 * 10), (5 * 10 + 1) 과 같이 다른 방법으로도 같은 수를 만들 수 있어 중복 검사를 해줘야 한다.

소스 코드

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

public class Main {
    public static int N, answer;
    public static int[] nums = {1, 5, 10, 50};
    public static boolean[] visit = new boolean[1001];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        permutation(0, 0, 0);

        System.out.println(answer);
    }

    public static void permutation(int depth, int idx, int sum) {
        if (depth == N) {
            if (!visit[sum]) {
                visit[sum] = true;
                answer++;
            }

            return;
        }

        for (int i = idx; i < 4; i++) {
            permutation(depth + 1, i, sum + nums[i]);
        }
    }
}