[프로그래머스 동적계획법(DP)]타일 장식물- Python3

문제

https://programmers.co.kr/learn/courses/30/lessons/43104

코딩테스트 연습 - 타일 장식물 | 프로그래머스

대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개의 나선 모양처럼 점점 큰 타일을 붙인 형태였다. 타일 장식물의 일부를 그리면 다음과 같다.

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타낸다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면 다음과 같다.
[1, 1, 2, 3, 5, 8, .]
지수는 문득 이러한 타일들로 구성되는 큰 직사각형의 둘레가 궁금해졌다. 예를 들어, 처음 다섯 개의 타일이 구성하는 직사각형(위에서 빨간색으로 표시한 직사각형)의 둘레는 26이다.

타일의 개수 N이 주어질 때, N개의 타일로 구성된 직사각형의 둘레를 return 하도록 solution 함수를 작성하시오.

제한 사항

• N은 1 이상 80 이하인 자연수이다.

입출력

n = 5, return = 26

 

알고리즘

def solution(n):
    dp = [0] * (n+1)
    dp[0] = -1
    dp[1] = 1
    dp[2] = 1

    for i in range(3, len(dp)):
        dp[i] = dp[i-1] + dp[i-2]
    answer = 2 * (dp[-1] + dp[-1] + dp[-2])

    return answer

 

설명

LV3 문제이지만 매우 간단한 문제이다. 여러 방법이 있겠지만, DP를 사용해서 풀도록 하겠다. 

앵무조개에서 이미 감이 왔겠지만, 피보나치 수열의 응용문제이다. 각 변의 길이는 1, 1, 2, 3, 5, 8, 13, ...  이렇게 잘 알려진 피보나치 수열의 원소들을 그대로 따라간다. 그리고 우리가 원하는 n번째 타일까지의 둘레 값은 만들어진 배열 dp의 뒤에서 2개의 원소, 즉 dp[-1], dp[-2]으로 구할 수 있다. 

1. for문을 통해서 dp[i]의 값을 피보나치 수열의 값으로 채운다. 
2. 위의 문제 설명에서 볼 수 있듯이, 문제가 원하는 둘레의 길이는 마지막 원소의 값을 세로로, 마지막 원소 + 그 앞 원소의 값을 가로로 하는 직사각형의 둘레이다. 이는 2 * (dp[-1] + dp[-1] + dp[-2]이다. 이 값을 return한다.

혹시나 이전에 DP를 소개한 내용이 궁금하다면 아래 링크를 따라가보도록 하시오.

2020/01/30 - [공부/알고리즘] - [알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

[알고리즘 자습]동적계획법(Dynamic Programming) - 동전 선택, 거스름돈 만들기, 동전 줍는 로봇

 

결과

올바른 값을 출력한다.

 

후기

DP활용에 입문하는데 아주 좋은 문제라 생각한다. 문제가 아주 만만한 것이 거침없이 풀린다. 다만 늘 풀던대로 풀려고 하지 말고, DP를 꼭 적용해서 풀길 바란다.