[백준] 1904번 : 01타일

요새 DP를 공부하고 있는데 하는 겸사겸사 비슷한 문제들 위주로 풀어보고 있다.

문제를 보기 전까진 몰랐는데 보고 나니 이것도 피보나치의 연장선이라 좀 쉽게 해결한 것 같다.

 

 

접근법

- N이 5일 때까지를 각각 계산한 결과 1, 2, 3, 5, 8로 피보나치 형상인 것을 알 수 있었다.

- 왜 피보나치일까 고민을 해본 결과, 끝이 00인 경우 (N - 2)의 수와 끝이 1인 경우 (N - 1)를 더해주면 N일 때의 경우의 수가 나온다는 것을 알 수 있었다.

- 중간에 for문 안에서 %를 취해준 이유는 마지막에 %를 취해주게 되면 중간에 int값이 터질 수도 있어서 안에서 처리를 해줬다.

- 재귀로 돌리면 무조건 터지는 수이기 때문에 for문을 활용하여 넣어주었다.

 

 

 

풀이

#백준 1904번, 01타일
import sys

dp = [0 for _ in range(1000001)]
dp[1] = 1
dp[2] = 2

N = int(input())


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

print(dp[N])

 

 

 

결과