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

 

특정 수로 나누어 나머지 구하는 과정을 다른 방식으로 해주었더니 시간 초과를 해결하였다.

 

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

 

위 코드는 일부 효율성 테스트케이스에서 시간 초과가 발생하였다.

 

위 코드는 1000000007 로 나누는 과정을 마지막에만 해주었다.

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

1. 2 x n 타

수정한 위 코드는 1000000007 로 나누는 과정을 for문 내에 적용해주었다.

즉, dp[i] 값이 갱신될 때마다 적용하였다. 그랬더니 시간 초과 오류가 해결되었다.

 

시간 초과 발생한 이유는 각 단계에서 1000000007 로 나누는 과정을 하지 않으면 dp[i] 값이 매우 커져서 덧셈 연산 자체가 매우 느려지기 때문이다. 또한, 큰 값을 저장하고 계산하는 것은 메모리 사용량도 증가시키기 때문에 메모리 측면에서도 비효율적이다.

 

dp 문제를 풀 때, 마지막 값만 생각하지 말고 중간 과정에서의 값 변화도 생각해야겠다.

 

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스