프로그래머스 Lv3 타일 장식물

문제 풀이

 1. 간단한 dp 문제로, n번째 타일 장식물의 한 변의 길이 dp[n]에 대한 점화식은 다음과 같다.

 dp[n] = dp[n-1]+dp[n-2]

 2. 문제는 n번째 타일 장식물까지 붙였을 때, 가장 바깥의 둘레를 구하는 것인데, 예제에서 제시한 아래의 그림을 살펴보면, 계속 직사각형 형태를 띔으로 상하, 좌우의 길이는 각각 같다. 또한, 상하 또는 좌우의 길이 중 하나는 마지막 타일 장식물의 한 변의 길이가 되며, 나머지 한 변의 길이는 마지막 타일 장식물의 길이와 그 전 타일 장식물의 길이가 된다. 

예를 들면, 5개의 타일 장식물이 붙은 경우에는, 세로의 길이는 마지막 타일의 길이인 5 이고, 가로의 길이는 마지막 타일 장식물의 길이인 5에 이전 타일 장식물의 길이인 3을 더한 8이다. 6개의 타일 장식물을 붙였을 경우에는 가로가 8, 세로는 8(마지막 장식물의 길이)+5(이전 장식물의 길이) 인 13이 된다.

 따라서 n개의 타일 장식물을 붙였을 때의 둘레는 2*dp[n] + 2(dp[n]+dp[n-1]) 이 된다.

 

Python Code

def solution(N):
    dp = [1,1]
    for i in range(2,N):
        dp.append(dp[-1]+dp[-2])
    if N==1 : return 4
    return (2*dp[-1])+(2*(dp[-2]+dp[-1]))

문제 링크

프로그래머스