코딩테스트/백준 코틀린

[6개월 안에 백준 플래티넘 달성하기] 15. 피보나치 수6 11444 해설

junjunjun 2023. 12. 31. 15:24
반응형

백준 Class4의 마지막 문제입니다.

 

마지막 문제인 만큼 꼭 풀고 싶었지만 결국 풀지 못하였습니다. 문제의 해설을 보고 이해하는 데까지 시간이 조금 걸렸습니다. 따라서 최대한 풀어서 해설을 작성해 보겠습니다.

 

참고로 행렬을 이용한 풀이가 아닙니다. 행렬을 이용한 풀이는 나중에 다시 푼다고 하더라도 도저히 생각해 낼 수 없을 거 같다고 판단을 하여서 좀 더 쉬운 풀이 방법을 작성하였습니다.

피보나치 수6 행렬 해설 블로그

 

피보나치 수 6 문제

문제

 

풀이

아마 여기까지 코테를 푸신 분들이라면 입력 가능한 n의 범위를 보고 바로 거듭제곱 관련 문제라는 것을 알아차리셨을 겁니다.

저도 마찬가지로 이를 이용하여 처음에는 제곱과 관련되어 규칙을 찾아보았지만 실패하였습니다.

 

해당 문제는 피보나치 식을 이용하여 약간의 응용과 규칙성을 찾을 수 있다면 풀 수 있는 문제입니다.

 

가장 먼저 피보나치 식

F(n) = F(n-1) + F(n-2) 에서 뭔가 규칙을 찾아줘야 합니다.

그러기 위해서는 변환을 해줘야 되는데 우리는 F(n-1) = F(n-2) + F(n-3) 임을 알 수 있습니다.

 

따라서 

F(n) = F(n-2) + F(n-3) + F(n-2)

= 2F(n-2) + F(n-3)    

이 됩니다.

이를 반복적으로 진행해주면 아래와 같습니다.

 F(n) = F(n-1) + F(n-2)                                      // F(n-1) = F(n-2) + F(n-3)
      = F(n-2) + F(n-3) + F(n-2)    =>  2F(n-2) + F(n-3)     // 2F(n-2) = 2F(n-3) + 2F(n-4)
      = 2F(n-3) + 2F(n-4) + F(n-3)  =>  3F(n-3) + 2F(n-4)    // 3F(n-3) = 3F(n-4) + 3F(n-5)
      = 3F(n-4) + 3F(n-5) + 2F(n-4) =>  5F(n-4) + 3F(n-5)    // 5F(n-4) = 5F(n-5) + 5F(n-6)
      = 5F(n-5) + 5F(n-6) + 3F(n-5) =>  8F(n-5) + 5F(n-6)

 

이제 우리는 위의 식을 통해 규칙을 찾아주면 됩니다.

F앞에 있는 숫자들을 순서대로 보면 (2, 3, 5, 8) (1, 2, 3, 5) 가 나오는데 이는 피보나치 수의 순서와 동일합니다.

 

피보나치 수 표

인덱스 0 1 2 3 4 5 6 7
값 0 1 1 2 3 5 8 13

 

그러면 우리는 F앞에 있는 숫자들을 F() 형식으로 바꿔줄 수 있습니다. ex) 8 -> F(6)

 F(n) = F(n-1) + F(n-2)     => F(2)F(n-1) + F(1)F(n-2)
      =  2F(n-2) + F(n-3)   => F(3)F(n-2) + F(2)F(n-3)
      =  3F(n-3) + 2F(n-4)  => F(4)F(n-3) + F(3)F(n-4)
      =  5F(n-4) + 3F(n-5)  => F(5)F(n-4) + F(4)F(n-5)
      =  8F(n-5) + 5F(n-6)  => F(6)F(n-5) + F(5)F(n-6)

 

이제 각각의 식에 있는 상수에 어느 정도 규칙이 보이기 시작합니다.

2 1 1 2

3 2 2 3

4 3 3 4

5 4 4 5

6 5 5 6

k+1 k k k+1

해당 규칙에 따라 숫자에 k를 대입해 보면

 

 

이 나옵니다.

 

거의 다 왔습니다.

이제 n이 짝수일 경우 홀수일 경우를 분리하여 식을 만들어주면 됩니다.

 

n에 임의의 수 n이 짝수일 경우인 2k를 대입해 줍니다.

 

식을 간단히 해주기 위해 k에 k/2를 대입해 줍니다.

 

이 나옵니다.

 

마찬가지로 n에 임의의 수 n이 홀수일 경우인 2k+1을 대입해 줍니다.

 

 

식을 간단히 해주기 위해 k에 (k-1)/2을 대입해 줍니다. (2k+1 = k에 대한 결과)

 

 

모든 식이 완성되었습니다.

이제 F(n)에 대해서

  • n=0 일 경우 0
  • n=1 일 경우 1
  • n=2 일 경우 2
  • n=짝수 F(k/2){F((k+2)/2) + F((k-2)/2)}
  • n=홀수 F((k+1)/2)^2 + F((k-1)/2)^2

로 식을 짜주면 됩니다.

 

코드

fun main() {
    var n = readln().toLong()

    val div = 1000000007L

    val map = HashMap<Long, Long>()

    map[0] = 0
    map[1] = 1
    map[2] = 1

    fun solve(num: Long): Long {

        if (map.containsKey(num)) return map[num]!!

        var result = 0L
        // 짝수일 경우 = F(k/2){F((k+2)/2) + F((k-2)/2)}
        if (num % 2L == 0L) {
            val a = solve(num/2) % div
            val b = solve((num+2)/2) % div
            val c = solve((num-2)/2) % div
            result = a * ((b+c) % div) % div
        }
        // 홀수일 경우 = F((k+1)/2)^2 + F((k-1)/2)^2
        else {
            val a = solve((num+1)/2) % div
            val b = solve((num-1)/2) % div
            result = ((a*a)% div + (b*b)% div) % div
        }

        map[num] = result
        return result
    }
    print(solve(n))
}

 

 

 
반응형