[Algorithm] 1일1솔 - 백준 1904 01타일 (python3)

문제링크

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

 

문제설명

문제에 재귀 함수 코드가 주어져 있고, 그대로 구현하면 값을 구하는 데 시간이 매우 오래 걸린다는 힌트도 주고 있다.

문제풀이

a, b, c가 모두 같을 경우 a, b, c가 0 이하가 될 때까지 재귀를 돌게 되어 시간이 매우 오래 걸리므로, 메모이제이션을 활용하여 풀이했다.

 

n = int(input())

dp = [0] * 1000001
dp[1], dp[2] = 1,2
for i in range(3, n+1):
    dp[i] = (dp[i-1] + dp[i-2]) % 15746
print(dp[n])