<aside> 👉🏿 문제 링크

</aside>

문제 정리

<aside> 👉🏿 정수 n이 주어진다.

1,2,3을 더해 n이 나올 수 있는 방법의 수를 출력하라.

</aside>

# 입력값
3
4
7
10

# 출력값
7
44
274

접근 방법

<aside> 👉🏿 dfs방식으로 탐색을 하다가 조건을 하나 추가해 가지치기를 해나가는 방식으로 진행해보았다.

처음에는 2번 조건을 달지 않았었는데 모든 경우의수가 아닌 중복값을 제거한 경우의 수가 나왔다.

1. dfs로 탐색하여 합계가 n이 되는 지점에서 정답 처리를 한다.
2. 합계가 n보다 커지면 다음 depth를 건너뜀 처리해준다. </aside>

코드 진행

• 전체코드

<aside> 👉🏿 먼저 input() 함수를 생성한다.

readline()을 사용한다.

</aside>

import sys

# input보다 효율적인 readline 사용
def input():
    return sys.stdin.readline()

<aside> 👉🏿 테스트케이스와 n을 입력받는다.

1,2,3의 리스트와 결과값을 넣을 리스트를 추가해준다.

백트래킹 함수를 호출한다.

</aside>

t = int(input())

for _ in range(t):
    n = int(input())
    li = [1, 2, 3]
    results = []
    backtracking(0, [])
    print(len(results))

<aside> 👉🏿 인자인 c_sum은 누적 합계이다. 0부터 시작한다.

path는 결과값에 추가할 리스트를 생성한다. [] 빈 리스트 부터 시작한다.

1. 누적 합계인 c_sum이 n보다 클 경우에는 return으로 종료시킨다.
2. 누적 합계 c_sum이 n과 같아 정답인 경우 정답처리를 해주고 종료시킨다.
3. [1,2,3]을 돌면서 백트래킹 함수를 재귀호출해서 누적합계와 리스트를 이어나간다. </aside>

def backtracking(c_sum, path):
    # 합계가 n보다 클 경우 가지치기
    if c_sum > n:
        return
    # 합계가 n일 경우 정답 처리
    if c_sum == n:
        results.append(path)
        return
    # li를 모두 돌면서 백트래킹
    for i in li:
        backtracking(c_sum + i, path + [i])