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

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

9095번: 1, 2, 3 더하기

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

• 여기서 주의: 1이 처음 빠진다고 해서 두번째에도 1이 들어 갈 수 있다.
• for문을 n이 0이 될때까지 돌려주면 된다. 반복되는 과정이기 때문에 재귀함수로 구현가능

 

def sum(n):
    def dfs(n, arr):
        for i in [1,2,3]:
            if n-i == 0:
                result.append(arr+[i])
                return
            else:
                dfs(n-i, arr+[i])

    result = []
    dfs(n, [])
    return len(result)

• 계속 반복되면서 숫자를 저장 할 배열이 필요하다. arr 을 선언해주어 재귀함수로 호출될때 값을 같이 넘겨준다.
• n-i = 0이 되면 마지막 숫자를 추가해주고 반환이 되도록 한다.(종료조건)
• 아직 0이 되지 않는다면 재귀함수를 호출해준다.