제가 방금 문제를 풀었는데요.
제가 생각한 오류는 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로 인해 현재값이 중간에 삽입되기 때문)
이 두가지를 고려해야 풀리는 문제인거 같아요.
kingkk31 7년 전
증가부분수열과 감소부분수열을 써서 (증가부분수열 + 감소부분수열 - 1)의 최대값을 구하게 했는데 15퍼에서 틀렸다네요...
어디부분이 잘못된건가요? 제 알고리즘이 잘못됬나요??