백준 9095번- '1, 2, 3 더하기' (PYTHON 풀이)

문제:

 

수가 주어졌을 때, 어떤 방법으로 더해서 수를 만들 수 있는지 그 방법의 개수를 출력하는 문제이다.

 

풀이:

import sys

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

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

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

for _ in range(T):
    n = int(sys.stdin.readline())
    print(arr[n])

해당 문제는 DP 문제이다. 이전에 한 문제정도 DP 문제를 풀었던 것 같은데 비슷한 유형인 것으로 기억한다.

DP란 큰 문제를 해결하기 위해 해당 문제를 작은 문제로 쪼개고, 작은 문제의 정답을 저장해서 다시 쓰는 방법을 의미한다. 

그래서 일단 규칙을 찾기 위하여 초반 1,2,3,4를 직접 계산하였다.

 

n = 1	1	1개
n = 2	1+1, 2	2개
n = 3	1+1+1, 1+2, 2+1, 3	4개
n = 4	1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1	7개

여기까지 해보면 눈치가 빠른 사람은 규칙을 찾을 수 있을 것이다.

n을 만드는 모든 식을 생각할 때, 맨 마지막에 붙는 숫자는 1,2,3 중 하나이다.

그리고 마지막이 1이면 그 앞부분은 n-1을 만드는 방법, 마지막이 2이면 그 앞부분은 n-2를 만드는 방법, 마지막이 3이면 그 앞부분은 n-3을 만드는 방법이다.

즉, n을 만드는 방법 수는 dp[n]=dp[n-1]+dp[n-2]+dp[n-3] 이며, 여기서 dp[x]는 x를 만드는 방법의 개수라고 생각하면 된다.

 

앞서 말한 것처럼 dp는 작은 문제의 정답을 저장해서 다시 쓴다고 하였다. 그래서 필자는 코드에서 배열을 생성하였다. 예를 들어 n=10의 수를 구하려면 9,8,7이 필요하고 9를 세려면 또 8,7,6...이 필요하다. 이렇게 같은 값들을 계속 다시 계산하기 때문에 dp나 재귀를 활용해서 풀어야할 것이다. 그래서 배열에 한번 계산한 값들은 저장해두고 재사용한다.

그러므로 dp[1], dp[2], dp[3]에 직접 계산한 1,2,4의 값을 저장해두고 반복문에서 4 이상의 수들은 1,2,3번째 인덱스의 값을 활용하도록 코드를 작성하였다.

그리고 구하고자 하는 n을 넣었을 때 이미 계산된 인덱스의 값을 그대로 출력만 하도록 하여 해당 문제를 풀었다.