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

 문제

 

 

 문제 상황

 

- 직사각형의 타일로 특정 길이의 사각형을 만드는 방법의 수

 

 

 

 해결 전략

 

- 대표적인 dp문제로 피보나치의 개념을 활용한다.

 

- 어떤 길이 n의 타일을 구성하는 방법은 n-1의 길이 타일에 세로로 하나의 타일을 덧대는 방법, n-2길이 타일에 가로로 눕힌 타일 2개를 붙이는 방법 뿐이므로 dp[n] = dp[n-1] + dp[n-2]가 된다.

 

- 반복으로 해결한다.

 

- 재귀의 경우 오류 발생 가능성이 크다.

 

 코드

 

# 반복문을 활용
def solution(n):
    cache = [0 for _ in range(n+1)]
    cache[1] = 1
    cache[2] = 2
    for i in range(3,n+1):
        cache[i] = (cache[i-1] + cache[i-2])%1000000007
    return cache[n]
 
# 재귀를 활용
# 프로그래머스 런타임 에러
# 재귀는 깊어질 수록 오버플로우 가능성이 높다.
def solution2(n):
    cache = [0 for _ in range(n+1)]
    if n == 1 or n == 2:
        return n
    if cache[n] != 0 :
        return cache[n]
    cache[n] = (solution(n-1) + solution(n-2))%1000000007
    return cache[n]
 

 

 

 해설

 

- cache에 데이터를 쌓아가며 dp를 활용해 피보나치를 쌓아나간다.

 

 새로 학습한 것 & 실수 

 

- .

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/12900