백준 1904번 : 01타일

• 분류: 다이나믹 프로그래밍

코드

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int i=0, j=1;
    int idx = n;
    while(idx > 0) {
        int temp = j;
        j = (i+j)%15746;
        i = temp;
        idx--;
    }
    cout << j;
    cout << '\n';
}

• 코멘트
  
  이런 것도 다이나믹 프로그래밍이라고 할 수 있나?
  처음 문제를 보면 막막하다. 이게 뭐지?
  하지만 알고 나면 너무 쉽다. 그냥 피보나치 수열이다. 길이 n개짜리 이진 수열은 길이 (n-1)짜리의 왼쪽에 1을 붙이거나, 길이 (n-2)짜리의 왼쪽에 00을 붙여서 만들거나 둘 중 하나다.
  따라서 f(n)=f(n-1)+f(n-2)이고, f(1)=1, f(2)=2가 된다.
  다만 n이 최대 100만이기 때문에 재귀로 하면 안되고, 더 간단한 방법으로 해야 된다. O(n)짜리 훌륭한 방법이다.