[백준_15989] 1,2,3더하기 4 python

이런류의 문제를 여럿 풀어보았지만,

이건 아무리 봐도 규칙을 찾기가 어려웠다.

 

특히 dp를 풀때는 내가 지금 찾는 dp의 값이,

어디서 오는지를 찾아야하는데,

감이 잡히지 않았다.

 

결국 구글링을 통해 힌트를 얻었다.

 

앞으로 이런 문제를 만났을 때는,

어거지로 규칙을 찾아낼 수 있도록 해야할 것 같다.

# dp 설계
dp = [
    0 for _ in range(10001)
]

# dp 초기설정
dp[1] = 1
dp[2] = 2
dp[3] = 3

# dp 채워넣기
for i in range(4, 10001):
    
    dp[i] = dp[i-1] + (dp[i-2] - dp[i-3])

    # 보너스점수
    if i % 3 == 0:
        dp[i] += 1

# t 입력
t = int(input())
for _ in range(t):
    # n 입력
    n = int(input())
    # 출력
    print(dp[n])

이걸 어케찾아.,,,,