[프로그래머스] 2xn 타일링 (level2, python)

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

 

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

 

예를 들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

---

제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.
• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

---

입출력 예

---

입출력 예 설명

 

입출력 예 #1
다음과 같이 5가지 방법이 있다.

---

풀이 코드

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

다이나믹 프로그래밍 문제고, 백준(실버)에도 있는 문제다.

피보나치와 동일한 원리이며, 효율성을 통과하기 위해서는 두 가지 조건이 필요하다.

 

하나는 메모이제이션으로, 재귀를 사용하는 것보다 메모리 접근이 더욱 효율적이다.

두 번째는 최종적으로 값의 나머지를 구하는 것이 아니라, 배열에 삽입할 때 나머지 연산을 적용한다.

수가 커지면 커질 수록, 점점 더 빠른 속도로 커지기 때문에 중간에 나머지 연산을 적용해주면

수가 커져서 연산속도가 저하되는 현상을 억제할 수 있다.