[백준] 9095 _ 1, 2, 3 더하기 (Python)

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

9095번: 1, 2, 3 더하기

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 짜는 문제이다.

 

나는 이 문제를 모든  경우를 대입해보는 브루트포스 - 재귀 방법으로 풀어보았다.

 

go()라는 함수에는 합을 나타내는 sum과 문제에서 제공해주는 정수 n 값을 인자로 받는다.

 

함수의 종료 조건은 다음과 같다.

1) 1,2,3 들의 합(sum)이 n을 넘어가면 함수를 종료

2) sum과 n이 일치하면 우리가 찾는 결과이기 때문에 count를 +1 해준다.

 

sum이 아직 n보다 작다면 

1을 사용하면 go(sum+1, n)

2를 사용하면 go(sum+2, n)

3을 사용하면 go(sum+3, n)

 

코드는 아래와 같다.

# 문제: 백준 9095번 1,2,3 더하기
# 정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램
# 출력: 각 테스트 케이스마다, n을 1,2,3의 합으로 나타내는 방법의 수를 출력
# input.txt: 3 4 7 10 (첫 줄은 테스트 케이스 갯수)

import sys

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

T = int(input())
count = 0

# sum은 합, n은 문제의 입력 값
def go(sum, n):
    if (sum > n): # 수의 합이 목표 값을 넘어가면 함수 종료
        return

    elif(sum == n): #  수의 합이 목표 값과 같아지면 성공 횟수 +1
        global count
        count += 1
        return

    else:
        for i in range(1, 4):
            go(sum+i, n)

for i in range(T):
    n = int(input())
    go(0, n)
    print(count)
    count = 0

 

재귀함수가 헷갈렸는데 이 문제를 풀면서 정리할 수 있었다.