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

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

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

1+3

3+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

---

접근 방법: DFS, Backtrackting

import sys

def dfs(i, count):
    for num in range(min(3, i), 0, -1):
        if i - num == 0:
            count += 1
            continue
        count = dfs(i - num, count)
    return count

for _ in range(int(sys.stdin.readline())):
    print(dfs(int(sys.stdin.readline()), 0))

---

• 전체적인 재귀문의 흐름은 위 그림과 같다. dfs(i) 가 호출되면 i 값이 0이 될 때 까지 dfs(i-3), dfs(i-2), dfs(i-1) 을 재귀적으로 호출하는 방식으로 계속 i 값을 줄여나가다가, i 가 0이 되는 순간 count 를 1 올려주고 return 하는 방식이다.