[BAEKJOON/백준] 9095번: 1, 2, 3 더하기

 

---

[1] 풀이

 

 

어떤 숫자를 입력해도 원하는 대로의 결괏값이 나오게 하는 어떠한 단일한(?) 공식이 필요한가...에 대한 고민을 했었는데,

규칙에 대해 고민해본 결과 이 문제는 "DP"를 이용해서 푸는 문제다!

 

그러니까, 피보나치 수열처럼 큰 문제를 이미 답을 구한 작은 문제로 나누어서 풀이하는 방식을 사용한다는 것이다.

 

피보나치 수열은 f(n) = f(n-1) + f(n-2)과 같이 n번째 항이 n-1번째 항과 n-2번째 항을 더한 값인 경우였는데,

이 문제에서는 비슷하게 f(n) = f(n-3) + f(n-2) + f(n-1)와 같은 규칙이 적용이 된다. (단, N>3)

 

 

확인을 해보겠다.

 

 

1. n=4일 때,

4를 1, 2, 3으로 더하기 때문에, 1+3, 2+2, 3+1로 나눌 수 있다.

1+3	2+2	3+1
1+3 1+1+2 1+2+1 1+1+1+1	2+2 2+1+1	3+1

 

 

1+3은 3을 나타낼 수 있는 경우의 수와 같으므로 f(3)
2+2는 2을 나타낼 수 있는 경우의 수와 같으므로 f(2)
3+1은 1을 나타낼 수 있는 경우의 수와 같으므로 f(1)

 

f(4)=f(1)+f(2)+f(3)으로 나타낼 수 있다.

 

 

2. n이 5일 때,

5를 1, 2, 3으로 더하기 때문에, 1+4, 2+3, 3+2로 나눌 수 있다.

1+4	2+3	3+2
1+1+3 1+1+1+2 1+1+2+1 1+1+1+1+1 1+2+2 1+2+1+1 1+3+1	2+3 2+1+2 2+2+1 2+1+1+1	3+2 3+1+1

 

1+4은 4을 나타낼 수 있는 경우의 수와 같으므로 f(4)
2+3는 3을 나타낼 수 있는 경우의 수와 같으므로 f(3)
3+2은 2을 나타낼 수 있는 경우의 수와 같으므로 f(2)

 

f(5)=f(1)+f(2)+f(3)으로 나타낼 수 있다.

 

따라서 n을 나타내는 경우의 수는,

f(n) = f(n-3) + f(n-2) + f(n-1) (n>3) 와 같다.

 

 

---

[2] 코드

 

import sys
input = sys.stdin.readline

def func(x):
  if x==1:
    return 1
  elif x==2:
    return 2
  elif x==3:
    return 4
  else:
    return func(x-1)+func(x-2)+func(x-3)

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

 

 

---

[3] 느낀 점

 

자료구조 시간에 배웠던 재귀함수 개념을 실제로 코드로 구현해 볼 수 있었던 시간이었다.

세 단계 이전의 함수까지 호출하는 경우도 있는 경우를 보니, DP가 더 효율적이기만 하다면 네 단계 이전의 함수까지도 호출가능하지 않을까..? 하는 생각도 들었다.

C와는 다른 방법으로 입력을 반복해서 받아줄 수 있다는 것을 알게 되었다.

 

---

[4] 참고 자료

 

https://ggasoon2.tistory.com/39

https://velog.io/@greene/%EB%B0%B1%EC%A4%80-9095%EB%B2%88-1-2-3-%EB%8D%94%ED%95%98%EA%B8%B0-%ED%8C%8C%EC%9D%B4%EC%8D%AC

[백준] 9095번 1, 2, 3 더하기 파이썬