[백준/Python] 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.

 

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.

 

소스코드

def go(arr):
    global cnt

    if sum(arr) == n:
        cnt += 1
        return 
    
    for i in [1, 2, 3]:
        if not arr or sum(arr) + i <= n:
            arr.append(i)
            go(arr)
            arr.pop()

    return cnt

for _ in range(int(input())):
    n = int(input())
    cnt = 0
    print(go([]))

 

문제풀이

완전탐색(백트래킹)의 전형적인 로직이다.

1. 테스트케이스 T에 대해 반복하며 n을 입력받고, go 함수를 호출한다.

2. go 함수에서는, 만약 배열 arr의 요소들의 합이 n이라면 count 횟수를 증가시킨다. (arr에는 합이 n이 되도록 만드는 요소들이 있다.)

3. 만약 arr이 비어있거나, arr에 1, 2, 3 중 어떤 수 i를 더했을 때의 합이 n보다 작거나 같다면 arr에 i를 삽입하고 다시 go를 호출한다. 이후 다시 arr을 pop한다. (이미 해당 조합에 대해 count를 증가한 후 return된 것이므로!!)

4. 1, 2, 3에 대해 위 작업을 끝낸 후에 count 횟수를 return한다.

cnt를 재귀함수 식으로 구하고 싶었는데 어떻게 해야 할지 잘 떠오르지 않아서 그냥 전역변수로 선언하여 구했다😓