[백준 1904] 01타일 [C]

백준 - 1904

---

풀이

피보나치 수열과 같은 다음의 규칙이 존재한다.

N	2진 수열
1	1
2	11 00
3	111 100 001
4	1111 0000 1100 1001 0011
5	11111 11100 11001 10011 00111 10000 00100 00001

Dynamic Programming 방식 중 Memoization 방식으로 풀이했다.

---

소스코드

#include <stdio.h>
int main(){
    int N, dp[2] = {1, 2}, temp;
    scanf("%d", &N);
    if (N == 1){
        printf("%d", 1);
        return 0;
    }
    for (int i = 3; i <= N; i++){
        temp = dp[0];
        dp[0] = dp[1];
        dp[1] = (temp + dp[1]) % 15746;
    }
    printf("%d", dp[1]);
}

---

출처

1904번: 01타일