[python 파이썬] 백준 9507번 Generations of Tribbles

www.acmicpc.net/problem/9507

9507번: Generations of Tribbles

 

풀이1 - 메모이제이션 없는 재귀 - 시간초과

직관적으로 문제보고 짜봤는데 메모이제이션을 적용하지않아 시간초과 날 것 같았는데 돌려보니 시간초과가 났다 .

재귀 쓸거면 메모이제이션 적용해서 쓰자

t = int(input())

def koong(n):
    if n <2:
      return 1
    if n==2:
      return 2
    if n==3:
      return 4
    
    return koong(n-1) + koong(n-2) + koong(n-3) +koong(n-4)

for _ in range(t):
  n=int(input())
  print(koong(n))

 

풀이2 - 반복문을 이용한 풀이 - 맞음

t = int(input())

for _ in range(t):
  n=int(input())
  koong =[0]*(n+1)
  if n ==0:
    koong[0]=1
  elif n==1:
    koong[1]=1
  elif n==2:
    koong[2]=2
  elif n==3:
    koong[3]=4
  else:
    koong[0]=1
    koong[1]=1
    koong[2]=2
    koong[3]=4
    for i in range(4,n+1):
      koong[i]=koong[i-1] + koong[i-2] + koong[i-3] +koong[i-4]
      
  print(koong[n])