[Python] 9095 - 1, 2, 3 더하기

풀이

입력 받은 정수를 1, 2, 3의 합으로 나타내는 문제이다. 

이 문제를 해결하기 위해선 한 가지 규칙을 알아야 하는데, 바로 1, 2, 3을 제외한 모든 숫자는 DP로 표현할 수 있고, DP로 문제를 해결할 수 있다. 쉽게 말해서 정수 4의 경우는 총 7가지로, 1의 경우 + 2의 경우 + 3의 경우 = 1 + 2 + 4로 정해진다.

 

여기서 DP란? 다이나믹 프로그래밍의 약자로, 

DP를 설명하기 위해 가장 많이 활용되는 수식이 바로 피보나치 수열이다.

 

피보나치 수열이란? n번째 숫자는 n-1번째 + n-2번째 숫자로 구성된 수열이다.

결국 n번째 수를 구하기 위해선 이전의 수를 알고 있어야 하고, 이를 이용해 다음의 수를 예측(계산)할 수 있다.

 

DP를 활용해 코드를 작성하면 다음과 같다.

# 9095 1, 2, 3 더하기

n = int(input())

for T in range(n):
    n, i = int(input()), 4
    plus = [None, 1, 2, 4] # 0, 1, 2, 3의 값

    while i <= n:
        plus.append(plus[i - 1] + plus[i - 2] + plus[i - 3]) # 리스트의 이전 인덱스들의 합
        i += 1

    print(plus[n])