[백준] 9095번 (python 파이썬)

https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

import sys
cache = [0] * 11

cache[1] = 1
cache[2] = 2
cache[3] = 4

for i in range(4, 11):
  cache[i] = cache[i-1] + cache[i - 2] + cache[i - 3]

testcase = int(input())
for _ in range(testcase):
  print(cache[int(sys.stdin.readline())])

 

입력데이터의 범위는 11미만의 양의 정수이다.

여러 테스트 케이스를 갖는 문제이므로 최대 입력 데이터인 10으로 한번 계산 해놓고 캐쉬를 만든 후에

입력 데이터에 따라 캐쉬에 있는 데이터를 출력한다.

 

 

• 부분 반복 구조 : cache[ i ] = cache[ i - 1 ] + cache[ i - 2 ] + cahce[ i - 3 ]
• 최적 부분 구조 : 최적의 cache[ i - 1 ] 값과 최적의 cache[ i - 2 ] 값과 최적의 cahce[ i - 3 ] 값을 더하면 최적의 cache[ i ] 값이 나온다.  애초에 각각의 입력에 대해 한가지의 값만 가능하다.
• 메모이제이션 : 입력데이터의 범위가 1이상 11미만이므로 인덱스 0을 제외한 총 10개의 캐쉬를 만든다.
• 접근 방식 : cache[1]과 cache[2]와 cache[3]을 알고있으므로, bottom - up 방식을 이용한다.

다음은 top - down 방식으로 코딩한 코드이다.

import sys

testcase = int(input())
numbers = [int(sys.stdin.readline()) for _ in range(testcase)]

cache = [0] * (max(numbers) + 1)

def get_cache(n):
  if cache[n]:
    return cache[n]
  elif 1 <= n <= 2:
    cache[n] = n
  elif n == 3:
    cache[n] = 4
  else:
    cache[n] = get_cache(n-1) + get_cache(n-2) + get_cache(n-3)
  return cache[n]
  
for i in numbers:
  print(get_cache(i))