[BOJ] 9461. 파도반 수열

Python3,DP

문제

입출력

입출력 예시

주요 포인트

dp[i]와 dp[i+1]를 더한 값이 dp[i+3]이다.

계산하는 반복문을 먼저 두고, 입출력 반복문을 아래에 둠으로써 코드 반복을 막자

최종 코드

t = int(input())

dp = [0 for i in range(101)]

dp[1] = 1
dp[2] = 1
dp[3] = 1

for i in range(0, 98):
    dp[i+3] = dp[i] + dp[i+1]

for i in range(t):
    n = int(input())
    print(dp[n])

(+23/6/3)

t = int(input())

dp = [1 for _ in range(101)]

for _ in range(t):
    n = int(input())

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

    print(dp[n])

시간 84ms -> 48ms로 개선

피드백

규칙만 찾으면 어렵지는 않은 문제였다. dp[i]에 대입을 하려고 하니까 잘 안 됐다. 반복문을 4로 시작하는 것이 아니라 0부터 98까지 시작하는 문제였다.
그래도 처음 DP 문제를 풀었을 때와 달리 스스로 규칙에 대해 고민하고 요리조리 시도하고 있다. 조금만 더 수정하면 발전할 것 같다.