[코딩테스트] 프로그래머스 2 x n 타일링 파이썬(Python)

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

프로그래머스

def solution(n):
    num = 1000000007
    d = [1 for _ in range(n+1)]
    for i in range(2, n+1):
        d[i] = d[i-1] + d[i-2]
        d[i] = d[i] % num
    return d[n]

다이나믹 프로그래밍의 메모이제이션 방법을 사용하여 문제를 해결하였습니다.

직사각형을 채우는 방법의 수가 어떻게 증가하는지 확인하면 간단하게 해결할 수 있습니다.

n = 1

직사각형을 채우는 방법의 수는 1입니다.

n = 2

직사각형을 채우는 방법의 수는 2입니다.

n = 3

직사각형을 채우는 방법의 수는 3입니다.

n = 4

위의 예제와 같이 5입니다.

n = 5

직사각형을 채우는 방법의 수는 8입니다.

정리를 해보자면 다음과 같습니다.

n	1	2	3	4	5
방법의 수	1	2	3	5	8

 

규칙을 확인해보니 d[i] = d[i-1] + d[i-2] 인것을 확인할 수 있습니다.

• i가 0일때에는 1로 처리하였습니다.

i가 2부터 n+1 까지 순차적으로 증가하며 d[i]를 갱신하게 됩니다.

이때 d[i]를 계산하고 저장할 때 시간초과가 나는것을 방지하기 위하여 num으로 나눈 나머지를 저장하였습니다.

반복문이 종료되면 d[n]을 결과로 반환합니다.