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

출처 : 백준, https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

풀이

 

count = 0

def recursion(n):
  global count
  if not n:
    count += 1
    return

  for i in range(3, 0, -1):
    if n >= i:
      recursion(n-i)

for i in range(int(input())):
  recursion(int(input()))
  print(count)
  count = 0

 

재귀를 이용해 풀었다. 로직은 다음과 같다.

 

1. for문을 통해 3부터 1까지 감소하게 돌린다.

2. 들어온 수 n이 반복문의 수 i보다 크거나 같다면 n-i를 함수에 넣어 재귀적으로 호출한다.

3. 들어온 수가 0이라면 count를 증가시키고 return한다.

 

---

 

시간 복잡도

 

-

 

다른 사람의 풀이를 보면서 알게 된 점

 

DP를 이용한 풀이

(백준 - gkswnsgh2님의 풀이 참고)

 

n = int(input())
count = [1, 1, 2]

for i in range(3, n+1):
  count.append(count[i-1] + count[i-2] + count[i-3])

print(count[n])

 

DP과 재귀 중에서 어떤 걸로 풀어야할지 계속 고민하다가 점화식을 끌어내지 못해서 재귀로 풀었는데,

알고리즘 분류를 보니 DP더라.......그래서 다른 풀이들을 보니까 N=5까지 하면 점화식을 유추할 수 있게 된다.

점화식은......O(n) = O(n-1) + O(n-2) + O(n-3)이다........

 

이 풀이를 보면서 느낀게, 그 동안 DP를 구현할 때 count와 같은 배열 변수를 미리 n+1개를 선언해두고 

그 뒤에 초기 세팅으로 첫 번째나 두 번째 성분을 초기화해주었다.

이렇게 하니까 두 번째 변수를 3으로 설정했는데 input이 1이 들어오면 Index 에러가 나서 따로 처리를 해주어야했는데

위와 같이 배열에 append하는 방식으로 하면 그런 에러를 처리할 필요 없이 바로 적은 숫자에도 효율적으로 대응할 수 있더라.

 

 

고찰

 

문제를 보고 DP나 재귀 둘 중 하나까지 줄인게 성장했다고 생각한다.

둘 다로 풀 수 있던 것도 소름