[Baekjoon] 1904번 : 01타일

실버 3

1904번: 01타일

 

문제 풀이

남은 타일은 1하나로만 이루어진 타일, 0 두개로 이루어진 타일 한쌍이다.

n부터 써보면서 규칙을 찾아보면 다음과 같다. 즉, 피보나치 수열과 같은 형태로 진행됨을 알 수 있다.

n = 0, 1개
n = 1, 1개
n = 2, 00, 11 -> 2개 (1+1)
n = 3, 100, 001, 111 -> 3개 (1+2)
n = 4, 0011, 1100, 0000, 1001, 1001 -> 5개 (2+3)
n = 5, 00111, 10011, 11001, 11100, 00001, 10000, 00100, 11111 -> 8개 (3+5)

 

코드

n = int(input())
dp = [0] * (n+1)
dp[0], dp[1] = 1, 1

for i in range(2, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % 15746

print(dp[n])

 

느낀점

15746으로 나눈 나머지를 저장해주어야 메모리 오류가 나지 않는다.