가벼운 DP - 시간 복잡도를 고려한 (#9461번 파도반 수열)

#9461번 파도반 수열 https://www.acmicpc.net/problem/9461

9461번: 파도반 수열

 

수열 문제인 만큼 단번에 DP임을 알아차렸다!

 

처음에는 주어지는 테스트 케이스를 모두 저장할 때, 정렬을 진행하면서 저장했다.

그리고 리스트 가장 오른쪽에 있는 수 (가장 큰 수)까지 dp 계산을 진행하고 각각의 케이스에 맞는 값을 출력했는데

시간초과가 났다.

 

그래서 단순히 최댓값을 별도의 변수에 추가로 저장하고 진행했더니 통과했다.

 

틀린 코드 with 정렬 (시간초과)

n = int(input())
target = [int(input())]
for _ in range(n-1):
    x = int(input())
    for i in range(len(target)):
        if target[i] > x:
            target = target[:i] + [x] + target[i:]
    else:
        target.append(x)

dp = [0, 1, 1, 1] + [0]*(100-3)
for i in range(4, target[-1]+1):
    dp[i] = dp[i-2] + dp[i-3]

for t in target:
    print(dp[t])

 

정답 코드

n = int(input())
target = []
max_num = 0
for _ in range(n):
    x = int(input())
    target.append(x)
    max_num = max(max_num, x)
dp = [0, 1, 1, 1] + [0]*(100-3)
for i in range(4, max_num+1):
    dp[i] = dp[i-2] + dp[i-3]

for t in target:
    print(dp[t])