[백준/브루트포스] 9095 1, 2, 3 더하기(Python, 파이썬)

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

9095번: 1, 2, 3 더하기

 

문제의 조건은 간단하다. 숫자 n을 입력받고 1, 2, 3을 이용해 N을 만들 수 있는 경우의 수를 만들면 된다.

나는 이 문제를 두가지 방법으로 풀었다.

1. DP 테이블 활용

2. 재귀함수 활용

1. DP 테이블 활용

주어지는 N이 11보다 작은 수이기에 DP 테이블을 활용하여 충분히 풀 수 있을 것이라고 생각했다.

DP[i]에는 1, 2, 3 으로 i를 만들 수 있는 경우의 수가 들어간다.

예를들어, 4를 1, 2, 3으로 만드는 경우의 수는 다음과 같다.

 

1+1+1+1

1+1+2

1+2+1

1+3

2+1+1

2+2

3+1

 

이것은 곧,

1+(3 만드는 방법)

2+(2 만드는 방법)

3+(1 만드는 방법)

과 같다.

 

그래서 이를 이용하여 점화식을 만들면,

dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

이 된다.

 

코드로 나타내면 다음과 같다.

import sys
input=sys.stdin.readline

n=int(input())

arr=[]
for _ in range(n):
    a=int(input())
    arr.append(a)

dp=[0]*11
dp[1]=1
dp[2]=2
dp[3]=4

for i in range(4, 11):
    dp[i]=dp[i-1]+dp[i-2]+dp[i-3]

for i in arr:
    print(dp[i])

 

그러나 이 방법은 dp에서 초깃값으로 1, 2, 3까지는 지정해줘야한다는 문제가 있다.

이렇게 풀기 싫다하면 재귀함수를 이용하 푸는 방법도 있다.

 

2. 재귀함수 활용

재귀함수는 어떤 기준에 따라서 함수를 호출할지 결정해야한다. 

여기서는 사용한 수의 개수의 기준이다.

 

함수 go는 두 가지 인자를 받는다.

 

sum: 현재까지 더해진 값

goal: 입력받은 N

 

종료조건은 sum이 goal보다 크거나, 같을 경우이다.

sum이 goal보다 큰 경우에는 그냥 return 해주면 되고, sum이 goal과 같은 값일 때는 answer에 1을 더해준다.

 

함수 go는 다음 경우에 호출한다.

 

1을 사용하는 경우: go(sum+1, goal)

2을 사용하는 경우: go(sum+2, goal)

3을 사용하는 경우: go(sum+3, goal)

 

이를 코드로 나타내면 다음과 같다.

import sys
input = sys.stdin.readline

def go(sum, goal):
    if sum > goal:
        return

    if sum == goal:
        global answer
        answer += 1
        return

    now = 0

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

n = int(input())
answer = 0

for _ in range(n):
    goal = int(input())
    go(0, goal)
    print(answer)
    answer = 0