백준 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(1), V(5), X(10), L(50)을 조합하여 나올 수 있는 모든 수의 개수를 출력하는 문제

2. 배열로 1, 5, 10, 50을 담아준 다음 이 숫자들의 위치를 변경하면서 더하면 결과를 볼 수 있지 않을까 생각

3. TreeSet을 사용하여 중복되는 숫자들을 저장하지 않도록 구상하고

4. 반복문을 돌려 덧셈을 진행하였으나 시간 초과.

 

5. 결국 dfs를 사용해야 한다는 것을 인정하고 코드를 수정하기 시작하였음.

6. boolean형 배열 vistied 변수를 생성하여 조합하여 나올 수 있는 수를 배열 크기로 선언

7. 로마 숫자가 4개이므로 4번 반복하는 반복문 생성하여 깊이, 시작 값, 합계를 변경하며 반복시킨다.

8. 깊이가 사용할 수 있는 문자의 개수와 동일할 때 해당 합계가 방문하지 않았다면 result의 값을 증가하고 해당 boolean 배열을 false로 변경한다.

ex) N == 2, depth ==2

if(visited [11] == false){

    result ++;

    visitied [11] == true;

}

return

 

 

그림