jjjeju1202   3달 전

분명히 dp 결과값 맞는데 틀린 이유가 뭘까요... 결과는 "틀렸습니다" 라고 뜹니다 ㅠㅠ

flflds0811   3달 전

코드에 잘 못 된 부분이 있습니다.

점화식을 잘 못 이해하신 것 같습니다.

dp[x]는 x가 마지막 원소인 증가하는 부분수열의 중 가장 큰 증가 부분수열의 원소 수.

입니다. 그런데 원소의 수가 arr+dp가 될 수 없죠.

dp[x]=   max(1,max(dp[k]+1)) 이 됩니다.

여기서 k는 k<x ,  arr[k]<arr[x]를 만족하는 모든 k입니다.

다시 생각해보시고 코드 변경해보세요.

jjjeju1202   3달 전

성의 있는 답변 감사합니다. 일단 문제를 찾아봤는데 그게 문제가 아니라 5 4 3 2 1 처럼 감소수열만 있는 경우를 고려를 안 했었습니다..ㅎㅎ

아무튼 무사히 풀었습니다.

댓글을 작성하려면 로그인해야 합니다.