[프로그래머스 | Python] 2 x n 타일링

프로그래머스_2 x n 타일링

전형적인 dp인 타일링 문제

첫 번째 답안 코드

def solution(n):
    answer = 0
    dp = [0]*(n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = dp[i-2]+dp[i-1]
        
    return dp[n]%(int(1e9)+7)

이렇게 풀었을 때, 정확성 테스트는 모두 통과했지만 효율성 테스트에서 3개가 실패했다

두 번째 답안 코드

def solution(n):
    answer = 0
    dp = [0]*(n+1)
    dp[1] = 1
    dp[2] = 2
    for i in range(3,n+1):
        dp[i] = (dp[i-2]+dp[i-1])%(int(1e9)+7)
        
    return dp[n]

그런데 return 때 나머지를 구해주는 것이 아닌, 매 단계마다 나머지를 구해서 dp에 넣어주니 통과하더라
이유가 궁금해서 찾아봤는데 dp를 그냥 갱신하면 int값의 최대값을 넘어 오버플로가 날 수 있기 때문이라는 말이 있더라 (아마도 맞는듯..?)