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

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

 

 

[풀이]

정수 n에 대해, 1, 2, 3으로 덧셈 합을 만들 수 있는 경우의 수에 대해 구하는 문제였다.

1, 2, 3으로 쪼개서 재귀함수를 호출하였고, 4에 도달하면 전역변수 result에 +1을, 4를 초과하면 탈출하는 방식으로 진행했다.

 

 

[코드]

result = 0

def func(x, n):
    global result

    if x == n:
        result += 1
        return
    elif x > n:
        return

    for i in range(1, 4):
        func(x + i, n)

for _ in range(int(input())):
    result = 0
    n = int(input())
    func(0, n)
    print(result)

 

 

 

[시간복잡도]

O(3^n)