[BOJ] 01타일

---

코드

import sys
input = sys.stdin.readline

# N=1 (1, 00)
# 1

# N=2 (1, 00)
# 1(1)
# 00

# N=3 (1, 00)
# 1(00), 1(11) => 1(D[n=2])
# 00(1) => 00(D[n=1])

# N=4
# 1(100), 1(111), 1(001) => 1(D[n=3])
# 00(00), 00(11) => 00(D[n=2])

# ... N = 1(D[N-1)), 00(D[N-2])

N = int(input())
d = [0,1,2]
for i in range(N+1):
    if i <= 2:
        continue
    else:
        d.append((d[i-1]+d[i-2]) % 15746)

print(d[N])

결과

풀이 방법

• DP 문제이다
• N번째 01타일 수열은 '1'에 N-1번째 01타일 수열을 붙이고, '00'에 N-2번째 01타일 수열을 붙여서 만들어진다.
• 따라서 점화식은 D[N] = D[N-1] + D[N-2]이다.

---