[코딩테스트] 프로그래머스 - 2xn타일링 (Lv.3) in Python

세로길이가 2이고 가로길이가 n인 바닥이 있습니다. 이 바닥을 세로길이 1, 가로길이 2인 직사각형 타일로 모두 채우려 합니다. 예를 들어, 

n이 7인 바닥은 위와 같은 경우로도 채울 수 있습니다.

 

주어진 바닥을 채우는 경우의 수를 return하세요!

 

더 자세한 문제 설명 -programmers.co.kr/learn/courses/30/lessons/12900 

 

 

풀이

- 어렵게 생각할 것 없이, 피보나치 수열처럼 점화식으로 풀어내면 되는 문제이다!

- 예를 들어, [n = 3인 바닥]은 [(n=2)인 바닥을 채우는 경우의 수] + [(n=1)인 바닥을 채우는 경우의 수]이다.

- 따라서 solution(n) = solution(n-1) + solution(n-2).

 

- 여기서 중요한 점은, 재귀적으로 "만" 풀면 recursion depth가 너무 깊어지고, 같은 함수가 계속 호출되어 효율성을 떨어지게 하므로, 메모이제이션 (memoization)이 꼭 필요하다는 점이다.

- 또한, 이 문제에서는 최종적으로 n에 대한 점화식을 한 번만 풀면 된다.

- 따라서 재귀함수가 아닌 일반적인 for문으로 구하자!

 

 

파이썬 구현

 

def solution(n):
	nums = [0, 1, 2]
    
    for i in range(3, n+1):
        newNum = (nums[-1] + nums[-2])  % 1000000007
        nums.append(newNum)
        
    return nums[-1]