글 읽기 - 틀리게 나온 input을 알고 싶습니다.

ldg1291 6년 전 0

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

예제 input에 대해서는 잘 작동합니다.

감사합니다

#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(cnt1 >= k && cnt2 >= k) {
            right = mid-1;
        } else if(cnt1 < k && cnt2 < 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;
}

ljh6274 6년 전 0

문제에서 주어지는 N이 최대 10만인데요 n^2을 하게되면 오버플로우가 나게 됩니다.

하지만 이와 상관없이 문제에서 "k는 min(10^9, n^2)보다 작거나 같은 자연수이다." 라고 주어져서

N을 10억으로 놓고 하면 되네요

amugeona 6년 전 0

int right = n*n;

윗분께서 얘기하는 부분은 여기 코드입니다.

ldg1291 6년 전 0

모두 감사드립니다

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

문제

문제

출처

ICPC

틀리게 나온 input을 알고 싶습니다.

ldg1291 6년 전 0

ljh6274 6년 전 0

amugeona 6년 전 0

ldg1291 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말