문제
처음에는 문제를 완전히 잘못 이해했다
첫번째 징검다리부터 출발하여 이전에 밟은 돌보다 높이가 높은 돌이 나오면 이동하면서 개수를 세주는 방식으로 풀어주면 된다고 생각했기 때문이다.
해당 문제에 첫번째 돌부터 밟아서 출발한다던가 하는 조건이 없기 때문에 어디서 시작할 지는 경우에 따라 달라지는 것이다.
그래서 어디서 시작하든 모든 경우의 수에서 dp를 저장해 max값을 구해주면된다.
이를 정리해주면
import sys
n = int(input())
leg = list(map(int,input().split()))
dp = [1] * n
for i in range(1,n):
#i 이전의 돌에 대한 시물레이션
for j in range(i):
#현재 돌의 높이가 이전의 돌보다 높을때
if leg[j] < leg[i]:
#현재 돌을 밟는 것과, 이전의돌 + 현재돌을 밟을 때 둘 중 큰 값을 선택
dp[i] = max(dp[i],dp[j]+1)
print(max(dp))이렇게 된다.
