백준 9095번 1,2,3 더하기(Python, DP, Silver3)

백준 9095번 1,2,3 더하기 문제 바로가기

문제 접근

이 문제는 얼핏보면 완전탐색 문제로 볼 수 있다.
사실 완전탐색이 가장 쉬운 방법이긴 하지만 완전탐색의 경우에 모든 경우를 확인해야 하기 때문에 시간이 많이 걸린다.
예전에는 완전탐색으로 먼저 풀어보고 시간초과가 발생하면 다른 방법으로 풀어봤지만 이렇게 되면 푸는 시간이 너무 오래걸려서 좋지 못했다.
그래서 나는 완전탐색으로 보이는 문제는 DP로 먼저 생각해보는 습관을 들였다.
이 문제 역시 완전탐색으로도 가능하지만 DP로 먼저 생각해보았다.

문제 풀이

11미만의 n에 대해서 1,2,3의 조합으로 n을 만들어야 하는 문제이다.
n=4에 대해서 1+3과 3+1이 다른 경우로 취급되고 있기 때문에 수의 위치에 대해서도 다른 경우로 판단됨을 예제를 통해 알 수 있다.

따라서 이 문제를 작게 나누어 보면 마지막에 오는 숫자에 따라서 나눌 수 있게 된다.
1의 경우 1
2의 경우 1+1, 2
3의 경우 1+1+1, 2+1, 1+2, 3의 방식이다.
그렇다면 7의 경우에는 어떻게 나눌 수 있을까?
7일 때에는 마지막에 더하는 값이 3일 경우, 2일 경우, 1일 경우로 나뉜다.
마지막에 더하는 값이 3일 경우는 그 전까지의 값이 4여야 한다.
2일 경우는 5, 1일 경우는 6이다.
결국 7을 만드는 경우의 수는 6을 만드는 경우의 수 + 5의 경우의 수 + 4의 경우의 수와 같다.
결국에 이 3가지 경우를 모두 더한 값이 7일 경우가 되는 것이다.
이를 통해 아래와 같은 DP의 점화식을 세울 수 있게 된다.

dp[N] = dp[N-1] + dp[N-2] + dp[N-3]

이 점화식을 이용하여 바텀업 형식으로 DP에 값을 넣어주면 아래와 같이 완성할 수 있다.

제출 코드

import sys
T = int(sys.stdin.readline())
dp = [0 for i in range(12)]
dp[1] = 1
dp[2] = 2
dp[3] = 4

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

for i in range(T):
    n = int(sys.stdin.readline())
    # 중복을 허용한다.
    # 1+3, 3+1은 다른 경우이다.
    # 1로 끝나는 경우 + 2로 끝나는 경우 + 3으로 끝나는 경우를 합하는 DP테이블을 만든다.
    # 점화식 -> DP[n] = DP[n-1] + DP[n-2] + DP[n-3] = 1로 끝나는 경우 + 2로 끝나는 경우 + 3으로 끝나는 경우
    print(dp[n])