글 읽기 - 어떤 부분에서 틀렸는지 알 수 있을까요??

ldg1291 7년 전 0

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

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

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

mid가 답입니다.

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

cnt1 이 mid까지의 갯수이고

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

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int solve (int n, int k) {
     
    int right = n*n;
     
    int left = 1;
     
    int mid = 0;
     
    while(left <= right) {
         
        int cnt1 = 0;
        int cnt2 = 0;
         
        mid = (right+left)/2;
         
        for(int i=1; i<=n; i++) {
            cnt1 += min(n, mid/i);
            cnt2 += min(n, (mid-1)/i);
        }
         
        if(cnt1 >= k && cnt2 < k)
            break;
        else if(cnt2 >= k) {
            right = mid-1;
        } else if(cnt1 < k) {
            left = mid+1;
        }
    }
     
    return mid;
}
 
int main(int argc, const char * argv[]) {
     
    int N, K;
     
    scanf("%d", &N);
     
    scanf("%d", &K);
     
    printf("%d\n", solve(N, K));
     
    return 0;
}

sea5727 7년 전 0

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

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 7년 전 0

sea5727님

이분탐색입니다.

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

문제

문제

출처

ICPC

어떤 부분에서 틀렸는지 알 수 있을까요??

ldg1291 7년 전 0

sea5727 7년 전 0

tearsmore 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말