아이고야... 자문자답입니다.
주석 처리된 부분처럼 하려면 if(s>=e)가 아니라 if(s>e)여야 성립하네요. 아니면 if(s>=e)를 하고 e=mid로 설정하던가요.
기존 이분 탐색에서는 그냥 찾고자 하는 값이 없으면 "값 없음"하고 치워버리면 끝이지만, LIS에서 요구하는 이분탐색은 그게 아닙니다.
실제로 num이 존재하는지의 여부가 중요한게 아니라 어쨌든 덮어쓰기할 위치가 필요한거라, 범위에 숫자가 2개만 남았을 때 양쪽 모두를 비교해봐야 합니다. s와 e가 같아졌다고 냅다 값을 반환해버리면 1 2 3 5 7 9가 lis에 저장되어 있을 때, 6이라는 숫자에 대해서 이분탐색을 실행하면 1 2 3 6 7 9가 되어버립니다(원래는 1 2 3 5 6 9가 되어야 합니다).
만약 s와 e가 같아졌을 때 바로 답을 내고 싶다면 e=mid-1이 아니라 e=mid로 설정해서 여전히 mid가 들어갈 여지를 줘야 하는게 맞네요.
thre1009 2년 전
이분탐색을 사용해서 풀었습니다.
그런데 제가 아는대로 이분탐색을 만들어서 쓰니까 돌리자마자 틀렸습니다가 나옵니다. 주석 처리된 부분이 오답으로 나오는 코드입니다.
하는수없이 다른분이 쓰신 코드를 참고해보니 lis배열에 넣고자 하는 값이 중간값보다 클 때, 다음 이분탐색의 끝범위를 (중간값-1)이 아니라 그냥 중간값으로 설정하셨더라고요.
설마 이거때문인가 싶어서 그 부분만 바꿔서 제출했더니 맞았습니다가 떴습니다.
여기서 이유를 모르겠습니다. lis[mid]가 num보다 크면 lis[mid]와 num은 어차피 같지 않으니 범위에서 제외해도 될 것 같은데 왜 그렇게 하면 오답이 날까요?
많은 이분 탐색 예제 코드가 e=mid-1로 설정하고 있는데도 말입니다.