* 문제
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