1904 01타일

1. 문제

문제는 링크에 들어가면 있다.

2. 정답 코드

문제의 내 정답 코드는 다음과 같다.

import sys
read = sys.stdin.readline
N = int(input())

if N == 1 :
    print(1%15746)
elif N == 2 :
    print(2%15746)
else :
    dp_table = [0]*(N+1)
    dp_table[1] = 1
    dp_table[2] = 2
    for i in range(3,N+1):
        dp_table[i] = (dp_table[i-1]+dp_table[i-2])%15746
    print(dp_table[N])

3. 문제 풀이

이 문제는 간단한 DP 문제이다. 단 타일링 문제처럼 00과 1을 붙이기 위해 i-1, i-2번째를 합할 것인데 이때, i-2번째에 11을 사용하면 안되는 점을 잊지말자. 자세한 설명은 이전에 써놨으니 참고하자.