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

💻 문제 - S3

1, 2, 3의 3가지 숫자를 사용하여 정수 n을 만드는데 그 방법의 수를 구하는 프로그램이다. 문제에서 주어진 n이 4일 때를 다음과 같은 3가지 방법으로 나누어서 생각했다.

1. 마지막에 3이 더해지는 경우

   1+3

2. 마지막에 2가 더해지는 경우

   1+1+2
   2+2

3. 마지막에 1이 더해지는 경우

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

모두 더했을 때 7개 나오는 걸 확인할 수 있었다. 이때, 1번의 경우 마지막 1을 제외한 나머지 숫자의 합이 1이고 / 2번의 경우 마지막 2를 제외한 나머지 숫자의 합이 2이고 / 3번의 경우 마지막 1을 제외한 나머지 숫자의 합이 3이라는 것을 알 수 있다. 즉, dp를 [0,1,2,4]라고 초기화할 수 있으며 dp[n] = dp[n-3] + dp[n-2] + dp[n-1]라는 점화식을 얻을 수 있다.

👉 제출 코드

tc = int(input())
for _ in range(tc):
    n = int(input())
    dp = [0,1,2,4] + [0] * (n-3)
    for i in range(4, n+1):
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1]
    print(dp[n])

🙏 다른 사람의 풀이 보기

import sys
input = sys.stdin.readline
t = int(input())

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

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

for문 대신, 재귀를 사용하여 문제를 해결하였다.