[프로그래머스] 👷‍♀️ 타일 장식물 / 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.

반응형

저작자표시

'Algorithm > Problem Solving' 카테고리의 다른 글

[프로그래머스] 🖨 프린터 문제 / python  (0)	2019.02.18
[프로그래머스] 👨‍💻 기능 개발 / python  (2)	2019.02.18
[프로그래머스] 👷‍♀️ 타일 장식물 / python  (0)	2019.02.18
[프로그래머스] 👨‍🏫 정수 삼각형 / python  (0)	2019.02.18
[프로그래머스] ⚾ 숫자 야구 / python  (4)	2019.02.15
[프로그래머스] 🕵️‍♀️ 소수 찾기 / python  (0)	2019.02.15