13301 타일 장식물 Python 풀이 (100점)

13301

문제

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

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

입력

표준 입력으로 다음 정보가 주어진다. 입력은 한 줄로 구성되며 이 줄에는 타일의 개수를 나타내는 정수 N(1 ≤ N ≤ 80)이 주어진다. 

출력

표준 출력으로 N 개의 타일이 구성하는 타일 장식물 직사각형의 둘레를 출력한다. 

서브테스크

 

번호	배점	제한
1	21	N ≤ 7
2	53	N ≤ 40
3	26	원래의 제약조건 이외에 아무 제약조건이 없다(이 경우 64비트 정수형인 “long long” 자료형을 써야할 수 있음).

풀이 방법

위 그림은 피보나치 수열을 설명하는데 유명한 그림이다. 따라서 피보나치 수열 DP 문제랑 크게 다를것 없다고 생각하고 문제를 풀이하였다.

 

둘레를 구하는것이므로 살짝 비틀어서 규칙을 찾아보았다.

(1+1) * 2  = 4
(1+2) * 2 = 6
(3+2) * 2 = 10
(3+5) * 2 = 16
(8+5) * 2 = 26
(8+13) * 2 = 42

(1+1)2
  1 증가
(1+2)3
  2 증가
(3+2)5
  3 증가
8
  5 증가
13
  8 증가
21

S(i-1) : (n - 1, k - 1) = R(j-1) 일때
if S(i-1)이 짝수번이면
S(i) : (n-1, R(j-1)) = R(j)

if S(i-1)이 홀수번이면
S(i) : (R(j-1), k-1) = R(j)

 

처음 생각한건 위 처럼 짝수와 홀수 나눠서 풀이하려 했으나 어차피 순서는 중요하지 않으므로 짝수 홀수 나누지 않고 풀이해도 된다는것을 깨달았다.

풀이 코드

i = int(input())
MEM = [0 for _ in range(i + 1)]
MEM[0] = 1
MEM[1] = 2

def solve(tesk):
    if tesk <= 1:
        return MEM[tesk]

    if MEM[tesk] != 0:
        return MEM[tesk]

    else:
        MEM[tesk] = solve(tesk - 1) + solve(tesk - 2)
        return MEM[tesk]
solve(i)
print(MEM[i] * 2)

결과