[BOJ]1904_01타일

📃 01타일

코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

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

풀이

• DP 문제는 적어도 n => 5 까지 직접 계산해 보면서 규칙을 찾아야겠다.

• 출력이 너무 커서 15746으로 나눈 값을 출력하게 되는데, 이 과정에서 주의해야 할 부분

  • 결과 값에만 나눠주는 게 아니라 반복문 안에서도 수시로 나머지 연산을 해 주어야 메모리 초과가 발생하지 않는다. (값이 int값을 초과하기 때문에 n = 1000000 일 경우 엄청나게 많은 메모리를 차지하게 된다.)