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

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

사실 해결 방법을 오랫동안 떠올리지 못해서 직접 경우의 수를 찾아서 규칙을 발견했다.

세로 길이가 2로 동일하기 때문에 가로의 길이만 신경써서 살펴보면 다음과 같다.

n=1인 경우, 세로 모양의 타일만 들어갈 수 있으므로 경우의 수는 1가지이다.

n=2인 경우, 2가지이다.

n=3인 경우, 3가지이다.

n=4인 경우, 5가지로 피보나치 수열의 규칙(f(n)=f(n-1)+f(n-2))과 동일한 것을 확인할 수 있었다.

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

다음과 코드를 작성하여 문제를 해결하였다.

하지만 처음 코드를 작성할 때는 아래와 같이 1000000007을 최종 부분에만 나눠줬었다.

차이점은 크게 없다고 생각했으나 런타임 에러가 발생하였다.

아마도 더하는 과정에서 숫자가 커져서 그런 것으로 생각하고 있다. (혹시 정확하게 아시는 분 있으시면 댓글로 알려주시면 정말 감사하겠습니당 !)

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

아무튼, 도저히 문제 해결 방법이 떠오르지 않을 때에는 직접 경우의 수를 찾아서 규칙을 알아내는 것도 좋은 방법일 듯하다.