BOJ 9095 1,2,3 더하기 python

이 문제를 보고 떠올렸던 생각은

1. 메모리가 낭낭하다

2. 어렸을 때 많이 했던 점화식 만들기와 형태가 유사하다

-> dp로 풀어야겠다!

 

였는데 사실, 테스트케이스를 보고 먼저 점화식을 예상한 다음에 이유를 생각해봤다. 이러면 안 된다!

1 -> 1 (1)

2 -> 2 (1+1, 2)

3 -> 4 (1+1+1, 2+1, 1+2, 3)

4 -> 7 (위 사진 참조)

...

 

어라?

An = An-1 + An-2 + An-3 아냐? -> 맞다.

예를 들어, 10을 만들기 위해서는 7을 만드는 가지수 + 8을 만드는 가지수 + 9를 만드는 가지수 를 더하면 된다.

사진에 있는 4를 만들기 위해서, 마지막 수를 제외한 앞 수들의 합이 같은 수들로 묶어보면

• 1
  • 1
• 2
  • 1+1
  • 2
• 3
  • 1+1+1
  • 1+2
  • 2+1
  • 3

위와 같이 나타낼 수 있다. 이 때, 어떻게든 n-3, n-2, n-1을 만들었다면, 마지막에 3, 2, 1 을 더해주기만 하면 된다!

---

import sys

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

input_list = []
for _ in range(T):
    t = int(sys.stdin.readline())
    input_list.append(t)

dp = [0] * (max(input_list)+1)

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

print(dp)

마찬가지로 An의 값을 담을 리스트를 할당한다. 메모리를 사용해서 연산 속도를 비약적으로 높이는 것이 dp의 핵심이다.

구현은 매우 간단한 문제다. 다만 점화식을 떠올리고 식으로 작성하는 부분이 조금 더 어려웠다.