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

문제 확인

프로그래머스

나의 풀이

• 가로 - 세로 길이가 정해져 있기 때문에 DP로 풀 수 있었던 문제다.
• N 번째 위치에서 가능한 타일링은 가로가 1인 경우(N - 1)와 가로가 2인 경우(N - 2), 총 2가지 이다.
• 이를 점화식으로 나타내면 아래와 같다.
  • DP[n] = DP[n - 1] + DP[n - 2]
• 추가로 오버 플로우를 방지하기 위해서, 연산 중간마다 나머지 연산을 진행했다.
• 이는 나머지 연산의 분배 법칙을 통해 가능하다.

# (n x 2) 바닥 채우기
# n 번째 바닥 
def solution(n):
    # 경우의 수 저장
    DP = [1, 2]
    for i in range(2, n):
        DP.append((DP[i - 2] + DP[i - 1]) % 1000000007)
    return DP[n - 1] % 1000000007