Softeer 징검다리 (난이도3)

정답 코드

N = int(input())
s = list(map(int, input().split()))

dp = [1 for i in range(3001)]

for i in range(1, N):
    max_value = 0
    for j in range(i):
        if s[i] > s[j] and dp[j] > max_value: 
        # 다음에 건널 돌다리는 무조건 큰 것만 가능하기에 이전의 값들 중 가장 큰 값을 가져온다.
            max_value = dp[j]
    dp[i] += max_value

print(max(dp))

사용한 알고리즘

가라로 만든 다이나믹 프로그래밍

배운 점

처음에 DP의 마지막만 신경 써는데 굳이 마지막까지 갈 필요가 없었다.
생각의 부족...