Programmers / 2단계 / 2 x n 타일링 / python

 

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

 

 

모범 답안

def solution(n):
    a, b = 1,1
    for i in range(n):
        a, b = b, a+b
    return a

 

동적 계획법의 문제이다. 

동적 계획법의 핵심은 점화실을 찾는 것이다.

점화식을 찾기 위해 예를 보면,

n = 1: 1 ...................................... -> 1
n = 2: 11, 2 ................................. -> 2
n = 3: 111, 21, 12 ........................  -> 3
n = 4: 1111, 211, 112, 121, 22  ....... -> 5

 

여기서 n = 1, 2는 조건에 들어가는 부분이므로 빼고 n = 3, 4를 보면, 

dp[3] = 3 = dp[1] + dp[2]

dp[4] = 5 = dp[2] + dp[3]

 

위와 같은 점화식을 얻을 수 있다.

 

 

참조

https://dev-note-97.tistory.com/146

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