백준 No.1904 [01타일]

// Baekjoon Online Judge No.1904 [01 타일]

---

   How to solve   

  복잡할 것 같아 보이지만 N에 1, 2, 3 ... 8 까지만 대입 해보아도 결국 피보나치수열을 이룬다는 것을 알 수 있다.

하지만 이 문제에서 고려해야하는 점이 두 가지 있다.

1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로      Time out 이 생기지 않을 방법으로 함수를 구현하여야 한다.  2. 아무리 unsigned long long 자료형을 가진다고 해도 1,000,000번째 피보나치수는 overflow를 발생시킨다.

"1. 피보나치 수열을 구하는 함수를 구현할 때 1,000,000번째 항까지 구해야 하므로
     Time out 이 생기지 않을 방법으로 함수를 구현하여야 한다."

  만약 <Recursive function>으로 피보나치 수열을 구하는 함수를 구현한다면, 결국 호출된 함수의 개수가 기하급수적으로 늘어나 결국 Time out이 발생할 것이다.

  아래 코드를 보면 알 수 있듯, <Dynamic Programming (동적 계획)>을 이용하여 구현한다면 Time out없이 구현할 수 있다. 물론, <Dynamic programming>의 특성상 불필요한 Memory의 소모가 있긴 하겠지만!

 

"2. 아무리 unsigned long long 자료형을 가진다고 해도 1,000,000번째 피보나치수는 overflow를 발생시킨다."

  피보나치 수열의 100번째 항의 값만 해도 354,224,848,179,261,915,075가 되고 이 숫자는 unsigned long long 자료형의 최대값인 18,446,744,073,709,551,615를 넘는다. 그렇다면 1,000,000번째 항의 값은 상상도 못 할 만큼 큰 숫자일 것이다. 따라서 unsigned long long의 자료형을 가지는 answer vector에는 피보나치 값을 그대로 넣지 못할것이다.

 

  우리는 결국 answer[N]을 15,746으로 나눈 나머지를 출력해야하기 때문에 answer[N]에 N번째 피보나치 수를 15,746으로 나눈 값을 넣는 것은 어떨까? 하는 생각을 가져볼 수 있다. 아래의 코드처럼 말이다. 아래 코드를 보면 answer[i - 1] % 15746 + answer[i - 2] % 15746 를 answer[i]의 값에 넣는것을 볼 수 있다.

 

  (answer[i - 1] + answer[i - 2]) % 15746 를 생각할 수도 있겠지만 (a + b) % c 의 값과 a % c + b % c의 값은 항상 같은건 아니라 이렇게는 쓰일 수 없다.

반례 : a = 3, b = 3, c = 2 (3 + 3) % 2 == 0 3 % 2 + 3 % 2 == 1

 

  마지막에 정답을 출력할 때엔 answer[N]이 아닌 answer[N] % 15746를 출력해야 한다.

  answer[N - 1] % 15746 + answer[N - 2] % 15746 의 값이 15,746보다 클 수가 있기때문에 answer[N] % 15746를 출력해야 한다는 것을 알 수 있을 것이다.

---

   Code   

#include <iostream>
#include <vector>
 
using namespace std;
 
int N;
vector<unsigned long long> answer(1000001);
 
int main() {
    answer[0] = 1;
    answer[1] = 1;
 
    for (int i = 2; i <= 1000000; i++) {
        answer[i] = answer[i - 1] % 15746 + answer[i - 2] % 15746;
    }
    
    cin >> N;
 
    cout << answer[N] % 15746;
}

---

※ 아직 운영 준비중인 블로그 입니다.