0927_Algorithm_9095_123더하기

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

초기 구상과정

• DP, 딱 봐도 DP
• 1,2,3으로 문제를 풀어야하니 1,2,3이 기저사례가 되겠다.
• '4를 풀면서 어떤 규칙으로 이 세가지를 조합해야하는 것인가?'를 찾아보자

초기 코드

import sys
input = sys.stdin.readline

for tc in range(int(input())):
    num = int(input())
    dp = [0, 1, 2, 4] + [0] * (num - 3)
    for i in range(4, num + 1):
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]

    print(dp[num])

1을 만드는 방법

• 1 > 하나

2를 만드는 방법

• 1 + 1 / 2 > 둘

3을 만드는 방법

• 1 + 1 + 1 / 2 + 1 / 1 + 2 / 3 > 넷

4를 만드는 방법은

• 1을 만드는 방법에 +3하면 되니 하나
• 2을 만드는 방법에 +2하면 되니 둘
• 3을 만드는 방법에 +1하면 되니 넷
  고로 7이다

이런 식으로 dp를 전개해나가면

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

이렇게 문제에 적용해서 전개해서 원하는 곳까지 나가면 답을 찾을 수 있다.

느낀점

처음으로 한방에 문제를 해결해서 너무 기분이 좋다!
DP 어려운데 잘 찾아보면 규칙을 찾을 수 있을 때 기분이 가장 좋다.