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

Problem

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

Solution

문제를 풀기에 앞서 각 값들의 규칙성을 파악해보면 하나의 값은 이전 3개의 값과 같다는 것을 알 수 있다. 이를 통해 점화식을 작성해보면 f(n) = f(n-1) + f(n-2) + f(n-3)과 같이 나타낼 수 있다.

code1 (bottom-up)

def solve(n):
    arr = [0, 1, 2, 4] # n=1~3까지의 값을 저장
    for i in range(4, n+1):
        val = arr[i-3] + arr[i-2] + arr[i-1]
        arr.append(val)
    return arr[n]


t = int(input())
for i in range(t):
    n = int(input())
    print(solve(n))

위 코드는 점화식을 bottom-up의 형태로 반복문을 사용해 해결한 것이다. arr 리스트에 1~3까지 값들을 우선 저장한 뒤 반복문을 돌면서 값을 더해나가는 것이다.

code2 (top-down)

def solve(n):
    arr = [0, 1, 2, 4]
    if 0 <= n <= 3:
        return arr[n]
    return solve(n-1) + solve(n-2) + solve(n-3)


t = int(input())
for i in range(t):
    n = int(input())
    print(solve(n))

위 코드는 해당 점화식을 재귀함수 형태로 나타내어 해결한 것이다.

Ref.

https://yongku.tistory.com/entry/백준-9095번-1-2-3-더하기-파이썬Python