1,2,3 더하기 4 – 실버 1

n = int(input())
a = []
for i in range(n):
    a.append(int(input()))
dp = [0 for _ in range(10001)]
dp[0], dp[1], dp[2], dp[3] = 1, 1, 2, 3
for i in range(4, 10001):
    dp[i] = dp[i-1] + (dp[i-2] - dp[i-3])
    if i % 3 == 0:
        dp[i] += 1
for i in a:
    print(dp[i])

 

중요한 건 점화식, 규칙을 찾는 것이다.

 

규칙을 찾는 게 너무 어렵지만 그걸 못 찾으면 문제가 풀리지 않는다.

 

결국 모든 경우의 수를 비교해서 규칙을 찾아야한다.

 

5와 같은 경우 2와 3의 경우의 수를 뺀 값에 4의 경우의 수를 더한 5가 경우의 수지만 6은 경우의 수가 7이다.

 

9도 마찬가지로 1을 더한 값이 나온다. 즉 3의 배수는 원래 규칙에 1이 더해진다.

 

이런 규칙성을 보면 동적계획법은 창의수학과 비슷한 듯하다.

 

조금씩 확실히 실력을 늘려나가자.