[백준 9095번] 1, 2, 3 더하기 -python

문제 링크

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

9095번: 1, 2, 3 더하기

풀이 

- bfs로 풀이

- n이 1일 경우 1 출력, n이 2일 경우 2 출력 

- 그 외의 경우 bfs 실행 

1. 큐에 1, 2, 3 삽입 

2. 큐에 원소가 있을 때까지 

큐에서 원소 하나를 빼서 n이면 cnt + 1 

원소에 3을 더한 값이 n보다 크지 않으면 큐에 삽입 

1, 2의 경우도 마찬가지로 더한값이 n보다 크지 않으면 큐에 삽입 

3. cnt 출력 

from collections import deque 

test = int(input())

for _ in range(test):
  
  n = int(input())
  
  if n == 1:
    print(1)
  elif n == 2:
    print(2)
  else:
    q = deque()
    
    for i in range(1,4):
      q.append(i)
    
    cnt = 0 
    while q:
      x = q.popleft()
      
      if x == n:
        cnt += 1 
      else:
        if x + 3 <= n:
          q.append(x+3)
        if x + 1 <= n:
          q.append(x+1)
        if x + 2 <= n:
          q.append(x+2) 

    print(cnt)

- dp로도 풀이가 가능하다. 

점화식 f(n) = f(n-1) + f(n-2) + f(n-3)

- 걸리는 시간은 dp의 경우 72ms,  bfs의 경우 88ms로 dp가 더 빠르다. 

test_num = int(input())

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

for i in range(test_num):
  n = int(input())
  result = sol(n)
  print(result)