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

문제 링크

www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

풀이

import sys

t = int(sys.stdin.readline())

def f(n, case=""):
    if n == 0:
        cases.append(case)
    else:
        for i in range(1, 3+1):
            if n >= i:
                f(n-i, case=case+str(i))

for i in range(t):
    n = int(sys.stdin.readline())
    cases = []
    f(n)
    print(len(set(cases)))

재귀함수를 이용하여 가능한 모든 경우를 다 구하여 중복을 제거한 것의 개수를 세었다.

 

문제를 풀고 난 뒤 이 문제의 분류를 보니까, 이 문제는 동적 프로그래밍(Dynamic Programming)으로 풀어야 하는 문제였다. 그래서 문제를 다시 풀어보았다.

 

f(n)을 정수 n이 주어졌을 때 방법의 수를 반환하는 함수라고 하자.

f(1) = 1, f(2) = 2, f(3) = 3이다.

f(4)는 f(3)의 경우에 +1을, f(2)의 경우에 +2를, f(1)의 경우에 +3을 한 경우의 수를 모두 더한 것이라고 볼 수 있다.

 

f(3)	f(2)	f(1)
1 + 1 + 1 1 + 2 2 + 1 3	1 + 1 2	1

 

f(4)
1 + 1 + 1 + 1 1 + 2 + 1 2 + 1 + 1 3 + 1	1 + 1 + 2 2 + 2	1 + 3

 

같은 방식으로 f(5)는 f(4)의 경우에 +1을, f(3)의 경우에 +2를, f(2)의 경우에 +3을 한 경우의 수를 모두 더한 것이라고 볼 수 있다. (처음에는 이러한 방식이 +1, +2, +3이 식 사이 사이에 들어가는 모든 경우를 따져야 하는 줄 알았는데, 이렇게 표로 그려놓고 보니 겹치는 경우가 하나도 없었다.)

 

즉, f(n) = f(n-1) + f(n-2) + f(n-3) (n>3)라는 점화식을 도출해 낼 수 있다.

import sys

t = int(sys.stdin.readline())

def f(n):
    if n == 1: return 1
    elif n == 2: return 2
    elif n == 3: return 4
    else: return f(n-1) + f(n-2) + f(n-3)

for i in range(t):
    n = int(sys.stdin.readline())
    print(f(n))