kingkk31   2달 전

증가부분수열과 감소부분수열을 써서 (증가부분수열 + 감소부분수열 - 1)의 최대값을 구하게 했는데 15퍼에서 틀렸다네요...

어디부분이 잘못된건가요? 제 알고리즘이 잘못됬나요??

제가 방금 문제를 풀었는데요.

제가 생각한 오류는 2가지가 존재하는거 같아요.

결론 부터 말씀드리자면 저같은 경우는 lis[i] + lds[i] - 1의 방식으로 이 문제를 풀었습니다. 

이때 i는 현재부터 끝까지의 lis와 lds의 최대 길이이구요.


1. 0부터 n까지 세는 방식이 아니라 n부터 0까지 세어야 합니다.

     - 이유는 전자의 경우 방식상 마지막 자리가 확정이 됩니다.  이경우 lis의 최소값이나 lds의 최대값을 알수 없어서 뒤에 현재의 가장 작은 기차보다 작은 기차를 알아내는 방법을 알아내는 것이 불가합니다. 

    - 하지만 후자의 경우로 lis, lds를 하면 현재 lis의 최소값이 현재 i 가 되어 현재 i로 부터의 lds를 구해줄 수 있어 작은 기차들을 붙이는 경우를 셀 수 있게 됩니다.


2.  lower_bound를 이용하는 방식이 아니라 n^2의 방식으로 lis, lds를 구해야 합니다. 

    - lower_bound를 이용한 N*logN 방식은 빠르긴 하지만 앞서 말한 lis에서의 현재의 최소값이 확정되지 않게 됩니다. (lower_bound로 인해 현재값이 중간에 삽입되기 때문)


이 두가지를 고려해야 풀리는 문제인거 같아요.

 


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