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

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

9095번: 1, 2, 3 더하기

 

| 문제 내용

기본적인 동적프로그래밍 문제. 1,2,3을 사용해서 주어진 숫자를 표현할 수 있는 가지 수 구하기

 

| 풀이

숫자를 나열해보면 fn = fn-1 + fn-2 + fn-3 이라는 규칙을 쉽게 찾을 수 있다.

이런 값이 나오는 이유는 n을 1, 2, 3으로 나타낼 수 있는 각 경우의 수를 구하려면 1 + n - 1, 2 + n -2, 3 + n -3 일때의 경우의 수를 구하면 되기 때문. 

Ex) n = 4 일 때, 4 = 1 + 3, 4 = 2 + 2, 4 = 3 + 1 로 나타낼 수 있고 각 경우의 수는 f(3) + f(2) + f(1)임

n = 5 일 때, 5 = 1 + 4, 2 + 3, 3 + 2 => f(4) + f(3) + f(2)

 

1) 사전 이용 (이전에 계산했던 값들을 memo에 저장해서 사용)

n = int(input()) # 숫자 개수

memo = {
    1: 1,
    2: 2,
    3: 4,
}
# fn = fn-1 + fn-2 + fn-3
def get_count(num):
    if num in memo:
        return memo[num]
    else:
        memo[num] = get_count(num - 1) + get_count(num - 2) + get_count(num - 3)
        return memo[num]

for i in range(n):
    print(get_count(int(input())))

2) 재귀로만 (n이 커지면 시간초과 에러)

n = int(input()) # 숫자 개수

# fn = fn-1 + fn-2 + fn-3
def get_count(num):
    if num == 1:
        return 1
    if num == 2:
        return 2
    if num == 3:
        return 4
    return get_count(num - 1) + get_count(num - 2) + get_count(num - 3)

for i in range(n):
    print(get_count(int(input())))

| 느낀점

DP 문제다 느낌은 오는데 규칙을 모를 땐 일단 각 경우의 수부터 나열해 보는 게 좋다. 왜 이런 규칙이 나오는 지는 나중에 생각..!