ldg1291   3년 전

이분탐색으로 풀었습니다.


mid-1 까지의 갯수가 k보다 작고

mid까지의 갯수가 k이상이라면

mid가 답입니다.

라는 아이디어로 했습니다.

cnt1 이 mid까지의 갯수이고

cnt2 가 mid-1까지의 갯수입니다.

sea5727   3년 전

답을 알려주는 댓글이 아니라 죄송합니다 ㅠ_ㅠ..

for(int i=1; i<=n; i++) {
            cnt1 += min(n, mid/i);
            cnt2 += min(n, (mid-1)/i);

        }

이 코드는 어떻게 구현한건가요??

직접 숫자써가면서 확인해보니까 i*j 보다 작은수를 찾을 수 있겠던데

N * N 배열에서 i*j 보다 작은 수의 갯수를 2중반복문 돌려서 count하니까 시간초과가 나더라구요...

방법을 찾던중에 질문자님의 소스를 보고 분석해봤는데 알맞게 찾아지더라구요. 그런데 원리가 뭔지를 모르겠네요 ㅠ_ㅠ...

원리가 뭔가요??

tearsmore   3년 전

sea5727님

이분탐색입니다.

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