[ 백준 11366번 ] Tons of Orcs, no Fibbin’

1. 문제

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

 

2. 풀이

앞선 두 년도의 오크 숫자가 누적해서 더해지는 구조로, 각 년도별 오크 수의 점화식을 세워보면 아래와 같다.

년도	오크 수
1	a + b
2	a + 2b
3	2a + 3b
4	3a + 5b
5	5a + 8b

a와 b의 차수가 각각 피보나치로 증가하는 구조이고, a의 차수는 b의 차수보다 하나 작은 것을 발견할 수 있다. 즉, 단일 피보나치 배열을 미리 생성해두고, 입력받은 쿼리에 따른 출력을 구현하면 O(N)에 처리할 수 있는 문제.

가장 중요한 조건이자 검토해야할 사항은 입/출력의 범위가 Integer를 넘어서지 않는다는 것과, 오크가 한 마리도 없는 경우는 어떻게 할 것인가 라는 점이다.

3. 소스코드

fun main() {
    val fibo = generateSequence(Pair(1L, 1L)) { (a, b) -> Pair(b, a + b) }
        .map { it.first }
        .take(47)
        .toList()

    while (true) {
        val (a, b, c) = readln().split(" ").map { it.toInt() }
        if (a == 0 && b == 0 && c == 0) {
            return
        }

        println(if (a == 0 && b == 0) 0 else fibo[c - 1] * a + fibo[c] * b)
    }

}