[DP] softeer 징검다리

https://softeer.ai/practice/6293

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

 

꼭 제일 왼쪽 돌 부터 시작하는 문제가 아니었다.

어떤 위치에서 시작하든 높은 위치로 옮겨갈 수 있다.

 

증가하는 부분 수열을 찾아야 하며, 가장 긴 길이를 찾는 것이 목표 ==> LIS 문제 한다.. ==> 해결법은 DP 알고리즘

import sys
input=sys.stdin.readline

n=int(input())
stone=list(map(int,input().split())
dp=[1]*n

for i in range(1,n):
	for j in range(i):
    	if stone[j]<stone[i]: #증가하는 수열이 가능한 경우
        	dp[i] = max(dp[i],dp[j]+1)
            
print(max(dp))