hnryu   1년 전

어떠한 예외가 있는지 모르겠습니다.... ㅜㅜ 조언부탁드립니다.

sksdong1   1년 전

아래 조건에 잘못된 부분이 있어여

hnryu   1년 전

어떤부분이 어떻게 잘못되었는지 ...ㅠㅠ 설명해주실수 있나요??

sksdong1   1년 전

그냥 틀린 부분만 수정하면 dp[j] >= dp[i]로 바꿔 주면 됩니다.

이유를 설명하면

최장 감소 수열을 구하기 위해서 A[i] < A[j] 인 경우 ( j < i ), i번 인덱스는 j번 인덱스의 수보다 작기 때문에 j번 인덱스의 감소 수열의 길이 +1이 될 수 있음을 알 수 있죠. 이 때 둘 중 더 긴 것을 구해야 겠죠. 따라서 dp[i] = max(dp[i], dp[j]+1)가 이것의 의미가 되고, dp[j] < dp[i] 인 경우는 무조건 dp[i]를 택해야 합니다. 따라서 위의 조건이 틀렸습니당.  


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