[일반] 백준 1300 K번째 수 맞왜틀 한번만 봐줄 고수형 없어?

[laniake..(heecheon92)]

http://boj.kr/f52df3b5c4744c03a56c937a7c748f20

Baekjoon Online Judge

이분 탐색 할때마다 항상 햇갈리는게

lo 냐 hi 냐를 정하는 거랑.

어디서 본건 있어가지고 while (lo + 1 < hi) 이런식으로 자주 쓰거든

근데 45%쯤에서 틀렸다고 나오는데 반례도 못찾겠어.

내 소스가 어디가 잘못된걸까?

문제 링크:

https://www.acmicpc.net/problem/1300

Baekjoon Online Judge

[EN_SA(encludingsalt)]

1. 범위 한칸 더 넓게 잡아야 r이 전부 커버되고
2. pow좀 갖다버립시다 우리
http://boj.kr/7994610d8924474092a769a96366d1d8

[laniakea(heecheon92)]

헐 너무너무 감사. Lo hi범위 설정은 둘중 하나는 답이 가능한 범위보다 크게 설정해야 하는거야? - dc App

[EN_SA(encludingsalt)]

아래에 열심히 설명해줬는데... 조금 직관적인 설명을 덧붙이자면, r을 답으로 할라면 r이 1부터 n²까지 전부 움직일 수 있어야하고, 그럴라면 l이 0까지는 땡겨줘야 r이 1도 될 수 있겠죠?

[익명(61.105)]

이분탐색 소스코드는 뭐 하나 잡고 걍 외우셈

[익명(61.105)]

파이썬 bisect 라이브러리는 lo=0, hi=length(arr)임. 제로인덱싱에 길이가 10이면 arr[10]은 애초에 존재하지 않으니 이용 가능한 인덱스보다 1 크게 잡는다로 외우고 있음 난.

[laniakea(heecheon92)]

ㅇㅋㅇㅋ 땡큐. 참고할게! - dc App

[익명(221.141)]

이분탐색을 lo+1 < hi로하려면 lo =-1, hi=len(arr)로해야됨

[laniakea(heecheon92)]

아 그러면 lo, hi 둘다 답이 가능한 범위 밖에서 시작해햐 한다는 뜻이지? - dc App

[노는게제일좋아(aig0016)]

어디서 본 게 아마 이거 일텐데,
https://www.acmicpc.net/blog/view/109
저
코드에서 lo나 hi 둘 중 하나는 답이 가능한 범위 안에서, 하나는 밖에서 놓고 시작함
이분탐색은 구간이 TT...TTFF...FF 꼴로 표현할 수 있어야 사용할 수 있기 때문

[익명(220.76)]

둘 다 밖에 놓으면 안되는거임??

[노는게제일좋아(aig0016)]

둘다 밖에 놓아도 이분탐색만 잘 구현하면 문제 없을듯...? 내가 적은 건 링크 내용 적어놓은 거라