[BOJ] 16922. 로마 숫자 만들기(JAVA)

📌문제

문제

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

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

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

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

입력

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

출력

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

---

💪아이디어

1. 숫자 카드 조합구하기
   • I, V, X, L 숫자 카드를 이용해서 N개의 숫자 카드로 만들 수 있는 서로 다른 수의 개수를 구해야한다.
   • 숫자 카드는 중복해서 사용할 수 있으므로 중복조합을 이용해서 N개의 숫자 카드로 만들 수 있는 서로 다른 수의 개수를 구한다.
   • 중복조합을 이용해서 N개의 숫자 카드로 만들 수 있는 서로 다른 수의 개수를 구한다.
2. N-1조합이 담긴 before과 N조합이 담긴 after set사용
   • 숫자 카드의 합이 중복되지 않게 하기 위해 set을 사용한다.
   • before에는 N-1개의 숫자 카드로 만들 수 있는 서로 다른 수의 개수를 저장하고, after에는 N개의 숫자 카드로 만들 수 있는 서로 다른 수의 개수를 저장한다.
3. N이 0이 아닐때까지 반복
   • N이 0이 될 때까지 2번 과정을 반복한다.
   • before에 after을 복사하여 N개의 숫자 카드 조합을 저장한다.
4. before의 사이즈 수 출력
   • N개의 숫자 카드로 만들 수 있는 서로 다른 합의 개수 출력한다.

🥂코드

import java.io.*;
import java.util.*;

public class Main {

  static final int[] nums = {1, 5, 10, 50};

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    Set<Integer> before = new HashSet<>();
    Set<Integer> after = new HashSet<>();
    before.add(0);
    int N = Integer.parseInt(br.readLine());
    while (N-- > 0) {
      for (int sums : before) {
        for (int num : nums) {
          after.add(sums + num);
        }
      }
      before = Set.copyOf(after);
      after.clear();
    }
    System.out.println(before.size());
  } // end of class
}// end of main