[BOJ] 11444 피보나치 수 6 (C/C++)

11444번: 피보나치 수 6

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

---

진짜 오랫동안 틀렸습니다 상태로 방치되어 있던 문제다. 오늘도 이 문제를 풀려고 푼 건 아니고 다른 문제를 풀다 보니 분할 정복을 사용한 거듭제곱이라는 태그가 붙어있길래 이 문제에 똑같은 태그가 붙어 있던 것이 생각나서 이 문제를 먼저 풀기로 했다. 예전에 틀린 채로 방치해둬야겠다는 생각을 했을 때에는 행렬이 어색하기도 하고, 수학 태그가 붙은 문제를 풀기 싫어서 내버려두었었다. 잠깐 문제를 찾아봤을 때도 이게 뭐야 싶어서 한 10초 구경하다가 때려치웠던 기억이 있다. 그런데 언제까지 틀린 채로 내버려둘 수도 없고, 다른 문제를 푸는데 도움이 될까 싶어서 마음을 바꿨다.

 

우선 이 문제를 풀기 위해서는 행렬  곱으로 어떻게 피보나치 수를 구할 수 있는 지부터 알아내야 한다. 자력으로 알아낼 수 없으니 바로 구글링을 했다. 아래의 블로그에서 굉장히 친절하게 알려준다. 

[백준] 11444번 : 피보나치 수 6 - JAVA [자바]

선형대수 수업을 들었지만 아직도 행렬이 낯설다. 코딩을 하다보면 행렬을 피할 수 없는데, 아직도 낯가리는 사이라 힘들다. 행렬이랑은 친하면 친할수록 좋은 것 같다.

 

피보나치를 행렬을 통해 구할 수 있다고 하더라도 무지성 제곱을 하면 시간 초과를 피할 수 없다. N은 0을 세기도 귀찮을 정도로 큰 수까지 들어올 수 있다. 따라서 태그에 붙어있던 것처럼 분할 정복을 사용해야 한다. 이 또한 위의 블로그에서 친절하게 알려줬다. 내일은 그 문제를 자력으로 풀어봐야겠다. 

 

 

후기)

오늘부터 전화 영어도 시작했다. 취업하려면 영어 성적이 필요하다. 그런데 요새는 거의 말하기 시험 성적이 필요하더라. 언제까지 영어를 버벅거릴 수는 없으니 이제서야라도 시작해야지.