[백준] | JAVA, 자바 | 16922번 - 로마 숫자 만들기

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

 

---

문제 요약 :

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

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

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

 

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

---

문제 풀이 :

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

public class Main {
    static int n, result = 0;
    static int[] roma = {1, 5, 10, 50};
    static boolean[][] mixRoma = new boolean[21][1001];

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

        generate(0, 0);

        System.out.println(result);
    }

    private static void generate(int count, int value) {
        if (count == n) {
            if (!mixRoma[count][value]) {
                mixRoma[count][value] = true;
                result++;
            }
            return;
        }

        if (mixRoma[count][value]) return;

        mixRoma[count][value] = true;
        for (int i = 0; i < 4; i++) {
            generate(count + 1, value + roma[i]);
        }
    }
}

 

1. 변수 n, result 생성

2. 이 문제에서 사용하는 문자 I, V, X, L을 1, 5, 10, 50으로 배열 생성

3. boolean 2차원 배열 mixRoma 생성

(HashSet으로 사용해서 문제를 풀어봤지만 시간 초과로 boolean 2차원 배열을 사용하는 방법으로 수정했다.)

4. 문자의 개수 N 입력받기

5. 함수 generate에 count, value 값 0, 0을 주고 실행

5 - 1. count가 n과 같을 때 만약 mixRoma[count][value] 값이 false라면 true로 변경해 주고 result ++

5 - 2. 만약 mixRoma[count][value]가 true라면 return

5 - 3. for문을 사용해 함수 generate에 count, value 값 count + 1, value + roma[i]을 주고 실행 (재귀)

6. 저장된 result 출력