* 문제

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


* 풀이

https://github.com/stack07142/BOJ/blob/master/BOJ%231003_FibonacciCount/src/Main.kt


var dp = Array(41) {
Node()
}

fun main(args: Array<String>) {
var T = readLine()!!.toInt()

while (T-- > 0) {
val N = readLine()!!.toInt()
fibonacci(N)
println("${dp[N].count0} ${dp[N].count1}")
}
}

fun fibonacci(n: Int): Node {
if (dp[n].num != -1) {
return dp[n]
}
when (n) {
0 -> {
dp[n].num = 0
dp[n].count0++
}
1 -> {
dp[n].num = 1
dp[n].count1++
}
else -> {
dp[n] = fibonacci(n - 1) + fibonacci(n - 2)
}
}

return dp[n]
}

class Node(var num: Int = -1, var count0: Int = 0, var count1: Int = 0) {
operator fun plus(value: Node): Node {
return Node(num + value.num, count0 + value.count0, count1 + value.count1)
}
}


'Algorithm BOJ > DP' 카테고리의 다른 글

BOJ#1003 피보나치 함수  (1) 2018.05.28
BOJ#11049 행렬 곱셈 순서  (3) 2017.10.27
BOJ#1509 팰린드롬 분할  (0) 2017.10.27
BOJ#2352 반도체 설계  (0) 2017.10.09
BOJ#1495 기타리스트  (0) 2017.10.09
BOJ#2631 줄세우기  (0) 2017.09.28
블로그 이미지

stack.07142

IT, Android, Java, Algorithm. Kotlin, Swift, iOS

티스토리 툴바