[백준 BOJ_1904] 01타일 Python 풀이

출처: 백준 온라인 저지

문제

풀이

일단 1부터 6까지 만들 수 있는 2진수열을 아래에 나열해보았습니다.

• N=1: 1 (1)
• N=2: 11, 00 (2)
• N=3: 111, 100, 001 (3)
• N=4: 1111, 1100, 1001, 0011, 0000 (5)
• N=5: 11111, 11100, 11001, 10011, 10000, 00111, 00100, 00001 (8)
• N=6: 111111, 111100, 111001, 110011, 110000, 100111, 100100, 100001, 001111, 001100, 001001, 000011, 000000 (13)

1, 2, 3, 5, 8, 13… 피보나치 수열입니다.

N개의 타일로 만들 수 있는 2진수열의 가짓수는 N+1번째의 피보나치 수가 되기 때문에 결국에는 피보나치 수열 문제였습니다.

동적계획법으로 간단하게 구현한 뒤 N+1번째 수를 출력해줍니다.

코드

N = int(input())
cache = [-1 for _ in range(N+2)]
cache[0] = 0
cache[1] = 1
for i in range(2,N+2):
    cache[i] = (cache[i-2] + cache[i-1]) % 15746
print(cache[N+1])