[Softeer] 징검다리

문제

요약

돌의 높이가 갈수록 크도록 밟을 때, 최대 밟을 수 있는 개수는?

 

원본

https://softeer.ai/practice/6293

Softeer - 현대자동차그룹 SW인재확보플랫폼

풀이

머리에 DP라는게 뭔지 약간 흔적 정도는 남아 있어서 DP로 푼다는 건 알아 차렸다.

앞에서부터 값을 비교해서 키워나가는 건데 어떻게 했더라 하면서

풀이를 확인하고 나니 지웠던 풀이 방향이 맞았는데 더 생각해볼걸 아쉬웠다.

import sys
input = sys.stdin.readline

n = int(input())
lst = list(map(int, input().split()))

dp = [1] * n
for i in range(1, n):
    tmp = 0
    for j in range(i):
        if lst[j] < lst[i]:
            tmp = max(tmp, dp[j])
    dp[i] = tmp + 1
    
print(max(dp))