[백준/BOJ] 16922번: 로마 숫자 만들기

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

16922번: 로마 숫자 만들기

문제

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

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

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

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

입력

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

출력

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

해설

n개의 중복 조합을 구해 출력하면 된다.

중복 조합인 이유는 IV나 VI와 같이 순서가 다르지만 결국 같은 값이 되는 쌍이 있기 때문이다.

이미 그 값이 나왔었는지를 체크할 배열을 선언하여 아직 나오지 않았던 값일 때 개수를 증가시켜 준다.

소스 코드

val romaNum = arrayOf(1, 5, 10, 50)
val set = HashSet<Int>()
val visited = BooleanArray(1001)
var n = 0
var ans = 0

fun main() = with(System.`in`.bufferedReader()) {
    n = readLine().toInt()
    dfs(0, 0, 0)
    println(ans)
}

fun dfs(cnt: Int, start: Int, value: Int) {
    if(cnt == n) {
        if(!visited[value]) {
            ans++
            visited[value] = true
        }
        return
    }
    for(i in start until 4) {
        dfs(cnt+1, i, value + romaNum[i])
    }
}