[Kotlin] 백준 1354 : 무한 수열 2

문제 링크

1354번: 무한 수열 2

---

문제 해설

주어진 조건대로 재귀를 돌리면 된다. 다만 주어진 수의 범위가 굉장히 크기 때문에 피보나치 수를 재귀로 구할 때와 동일하게 별도의 Map에 이미 계산한 \(A_i\)를 저장하여 계산 횟수를 줄이는 것이 좋다.

Code

private val map = HashMap<Long, Long>()
private var p = 0L
private var q = 0L
private var x = 0L
private var y = 0L

fun main() = with(System.`in`.bufferedReader()) {
    val input = readLine().split(' ').map { it.toLong() }
    val n = input[0]
    p = input[1]
    q = input[2]
    x = input[3]
    y = input[4]
    map[0] = 1L
    println(sequence(n))
}

private fun sequence(n: Long): Long {
    if (n <= 0L) return 1
    return map[n] ?: (sequence(n / p - x) + sequence(n / q - y)).also { map[n] = it }
}