[SWEA/Python] 4869. 종이붙이기

📌 문제

https://swexpertacademy.com/main/main.do

SW Expert Academy

 

📌 문제 접근 방법

- 점화식 구하는 부분이 제일 어려웠다😭😭😭

• N이 10의 배수로 들어오지만, 10으로 나누어서 1, 2, 3... 이렇게 들어온다고 가정했을때,
  우선 N이 1과 2일 때는 다음과 같이 표현할 수 있다.
  

  

• 임의의 수 N이 입력되었을 때는 아래와 같이 표현할 수 있다.
  

  

  

•  이를 이용하여 점화식을 계산해보면,
  f(N) = f(N-1) + 2*f(N-2)
  가 나오게 된다. 2를 표현하는 방법은 2개이므로 N-2일때는 2를 곱해준다.

 

점화식만 구한다면 쉽게 풀린다!

 

📌 코드

import sys

sys.stdin = open('input.txt')

T = int(input())

for t in range(1, T+1):
    N = int(input())//10

    memo = [1, 3]

    if N > 2:
        for i in range(2, N):
            memo.append(memo[i-1] + memo[i-2]*2)

    print('#{} {}'.format(t, memo[N-1]))