[Python] BOJ 1904 - 01타일

https://www.acmicpc.net/problem/1904

1904번: 01타일

# N의 개수에 따라 일단 노가다로 직접 세보았다.

 

N = 1 -> 1
N = 2 -> 00, 11
N = 3 -> 001, 100, 111
N = 4 -> 0011, 0000, 1001, 1111, 1100
N = 5 -> 00001, 00100, 10000, 11001, 10011, 00111, 11100, 11111

 

# 1개, 2개, 3개, 5개, 8개, 13개... 그냥 피보나치수열처럼 이전 두개의 항의 값을 더하면 다음 항이 나온다.

처음에 우연의 일치인줄 알았지만, 다른 블로그들을 보다 깨달았다.

 

# n이 4일때의 값은 n이 2일때의 타일(00, 11)에 00을 더한 값과 n이 3일때의 타일(001, 100, 111)에

   1을 더한 값이므로 dp[4] = dp[3] + dp[2]이다.

   또한, n이 5일때의 값도 마찬가지로 n이 3일때의 타일에 00을 더한 값과 n이 4일때의 타일에

   1을 더한 값이므로 dp[5] = dp[4] + dp[3]이다.

   이 때문에 dp[n] = dp[n-1] + dp[n-2] 이라는 점화식이 나오고 피보나치 수열과 같아지게 된다.

 

import sys
input = sys.stdin.readline
N = int(input())
dp = [0]
dp.append(1)
dp.append(2)
for k in range(3, N+1):
	dp.append((dp[k - 1] + dp[k - 2]) % 15746)
print(dp[N])

(solved.ac 티어: 실버 3)