[백준 13699번] 파이썬 - 점화식

백준 13699 - 점화식

시간 제한 5초, 메모리 제한 512MB

# 조건

• 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자:
  • t(0)=1
  • t(n)=t(0)t(n-1)+t(1)t(n-2)+...+t(n-1)*t(0)
• 이 정의에 따르면,
  • t(1)=t(0)*t(0)=1
  • t(2)=t(0)t(1)+t(1)t(0)=2
  • t(3)=t(0)t(2)+t(1)t(1)+t(2)*t(0)=5
  • ...
• 주어진 입력 0 ≤ n ≤ 35에 대하여 t(n)을 출력하는 프로그램을 작성하시오.

입력

• 첫째 줄에 n(0<=n<=35)이 주어진다.

출력

• 첫째 줄에 t(n)을 출력한다.

# 접근 방법

• 점화식을 있는 그대로 구현해주면 된다.
• t[0] = 1로 설정해준 뒤 1부터 N+1까지 for문을 돌린다.
  • t(n)=t(0)t(n-1)+t(1)t(n-2)+...+t(n-1)*t(0) 이므로 각 곱하기의 왼쪽 번호와 n-i가 같은 경우를 제외하고는 같은 값이 2번씩 나온다.
• 따라서, left와 right를 0과 i-1로 설정하여 left == right가 아닌 경우에는 *2를 더해주고 같은 경우는 한 번만 더해준 후 nums 리스트에 추가해준다.

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

N = int(input())
nums = [1]

for i in range(1, N+1):
    left, right = 0, i-1
    val = 0
    while left <= right:
        if left == right:
            val += nums[left] * nums[right]
        else:
            val += (nums[left] * nums[right]) * 2

        left += 1
        right -= 1
    nums.append(val)
print(nums[N])