qkqhxla1   3년 전

아래의 lis함수는 인자를 리스트로 주면 lis를 구해서 리턴하는 함수입니다.

https://www.acmicpc.net/problem/2550 문제하고

https://www.acmicpc.net/problem/2565 문제를 아래의 lis함수를 그대로 써서 AC를 맞았기에

LIS함수가 문제가 없다는걸 확인했습니다. 그런데 바이토닉 수열을 구할때는 바로 0%에서 틀렸습니다가 뜹니다.

이거 왜 그런건가요?? 확인용으로 몇개 값을 출력해보면 다 잘나옵니다. 다른 소스로 풀긴 했는데 정말 궁금합니다. 

혹시나 백준님 봐주신다면 이거 틀린 케이스 데이터좀 주실 수 있는지 궁금합니다. ㅠㅠㅠ

궁금해서 미치겠습니다. 틀린 케이스라도 주시면 정말 감사하겠습니다.


c++로 고친 함수도 올리겠습니다.


cubelover   3년 전

LIS가 잘못되었습니다.

역추적을 저렇게 하면 안 됩니다.


반례로

9

2 3 4 1 2 1 4 3 2

같은 게 있네요. (답은 5)

cubelover   3년 전

아뇨 원소가 중복되지 않는 경우에는 올바르게 동작합니다. 2550번과 2565번 모두 원소가 중복되지 않기 때문에 올바른 풀이입니다.

다만 11054번 문제에서는 중복이 있어서 틀린 것이고요.

qkqhxla1   3년 전

아. 제가 이해가 부족했던것 같네요 한번더 살펴봐야겠습니다. 소스코드는 지우겠습니다

답답했는데 답변 정말 감사합니다!!.

qkqhxla1   3년 전

하나만 더 여쭤봐도 될까요?? 이 문제처럼 '중복이 있는 리스트'에서 lis '목록' 을 nlogn안에 뽑아낼수 있을까요??

구글링해도 안나오길래 궁금해서 여쭤봅니다... 된다면 키워드라도 주시면 감사하겠습니다..

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