Hama Develop

프로그래머스-타일 장식물, 파이썬

February 21, 2020

출처

문제설명

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

그림

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

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

제한 사항

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

입출력 예

N return
5 26
6 42

풀이

각 변의 길이는피보나치 수열을 이룬다. 고등학교 교과서에서 많이 봤던 그림이다.

피보나치 수열이 주어질 때, 직사각형의 둘ㄹ[ 길이를 구하는 문제다.

작은 예시를 생각해 보면서 패턴을 찾는게 경험상 가장 효과적인 방법 이었다.

1일때의 직사각형의 둘레 길이


1+1+1+1 = 4


2일때 직사각형의 둘레 길이


1+1+2+2 = 6


3일때 직사각형의 둘레 길이


2+2+3+3 = 10


4일때 직사각형 둘레 길이


3+3+5+5=16


5일때 직사각형 둘레 길이


5+5+8+8=26


슬슬 패턴이 보인다.

짧은변X2 + 긴변X2 가 정답이다. 짧은변과 긴변은 모두 1로 시작한다.

짧은변과 긴변을 모두 더한 값이 다음 차수의 긴변이 되고 현재의 긴변이 다음 차수의 짧은 변이 된다.

이를 n회 시행하도록 구현하면 끝이다.

나의 풀이

def solution(N):
    long = 1
    short = 1
    if N ==1:
        return 4
    for i in range(N-1):
        tmpshort = short
        tmplong = long
        short = tmplong
        long = tmpshort +tmplong
    border = short*2 + long*2
    return border

풀이는 맞기는 했지만, 문제의 의도와는 맞지 않을수 있기 때문에 다른사람의 코드를 좀 살펴보았다. (그냥 수학문제를 푼 기분이다.)

눈여겨 볼만한 풀이

문제의 취지에 맞게 다이나믹 프로그래밍으로 해결한 사람이 있었다.

def solution(N):
    dp = [0] * int(N+2) #메모이제이션을 위해 사용할 리스트 dp를 만든다. 
    if N == 1: return 4
    if N == 2: return 6
    dp[0], dp[1], dp[2] = 0, 1, 1
    for i in range(3, N+2): #메모 안에 피보나치 수를 기록한다.
        dp[i] = dp[i-1] + dp[i-2]
    return 2*dp[N-1] + 4*dp[N] # 꺼내서 쓴다.

원래 풀이에는 주석이 없었는데 내가 이해하기 위해 주석을 붙였다.

근데 여기서는 내 풀이랑 그렇게 효율성 차이도 없어서 이게 더 좋은 건지는 모르겠다.