[프로그래머스] 👷‍♀️ 타일 장식물 / python

👷‍♀️ 타일 장식물 문제 풀어보기

😃 나의 코드

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

DP(Dynamic Programming, 동적계획법)을 이용해 해결한 문제입니다. DP의 계획에 따라 전체 문제를 작은 부분으로 나누겠습니다. 최종적으로 구할 직사각형의 둘레는 마지막으로 구한 정사각형과 그 전 정사각형의 변의 길이를 통해 구할 수 있기 때문에 변을 구하는 문제로 치환해서 풀겠습니다.

가장 작은 정사각형부터 구하면 마지막으로 구한 정사각형의 한 변과 그 전 정사각형의 변의 길이 합이 구하고자하는 변의 길이입니다. 이는 rad_array라는 list 자료형에 저장되고, 다음 시행에서도 이를 사용하는 메모이제이션(memoization) 과정을 통해 마지막 정사각형의 변의 기리까지 구합니다. 최종적으로 구현 정사각형들의 변의 길이를 통해 구하고자하는 둘레를 구하면 문제는 해결됩니다.

Written with StackEdit.