글 읽기 - 이분탐색으로 풀었지만 최대수와 if문에서 의문점이 남습니다.

kangbada0728 5년 전 0

먼저 질문은 두가지 입니다.

long long right = k는 왜 가능한가?
while문 안의 if절에서는 왜 right=mid-1 대신 break;는 안되는가?

입니다.

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

먼저 배열 안에 들어갈 수 있는 최소수(left)와 최대수(right)를 잡았는데요...

저는 배열 안에 들어갈 수 있는 최대크기의 수가 N*N이라 생각해서 이를 right로 잡았는데 테스트해보니 그냥 k도 괜찮더라고요.

왜 괜찮은거죠? 전혀 모르겠습니다.

최대 크기의 수를 N*N 대신 k로 잡을 수 있다면 자료형 long long 대신 int를 쓸 수 도 있는 문제라 꼭 알고 싶습니다.

그리고 이분 탐색안의 while문에서는 먼저 중앙값(mid)보다 작거나 같은 수들이 총 몇개 있는지 for문을 이용하여 센다음 count에 저장했습니다.

count와 k가 딱 떨어진다면 바로 정답을 찾은거 아닌가요?

그렇게 생각해서 k와 count가 같다면 ans에 저장하고 바로 break해서 나갔는데 틀리다고 하더라고요.

하지만 대신에 right = mid-1을 넣으면 맞다고 하고요.

왜 이런지 궁금합니다.

이렇게 두가지 질문을 하고싶습니다.

아래 코드는 최종 통과한 코드를 올려놓았습니다.

#include <iostream>

using namespace std;

long long mini(long long a, long long b)
{
    if(a>b)
        return b;
    else
        return a;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    long long N=0, k=0;
    cin>>N>>k;
    
    long long left=1;
    long long right=k;// 질문1 : 선택할 수 있는 최대 숫자는 N*N이니까 right는 N*N이어야 하지 않나요? 왜 k로 해도 정답처리가 되는거죠?
    long long ans=0;
    while(left<=right)
    {
        long long mid = (left+right)/2;
        long long count=0;
        for(int i=1; i<=N; i++)
            count += mini(mid/i, N);
        
        if(k==count){
            ans = mid;
            right = mid-1;
            // 질문2
            // 왜 right=mid-1 대신 break는 안될까요?
            // 우연히 숫자 mid의 마지막이 k번째 숫자에 딱 걸릴수도 있잖아요.
            // 저는 그런 생각으로 break를 넣어서 딱 떨어질경우 그냥 정답으로 처리하게 하려고 했는데 20%정도에서 틀립니다.
        }
        else if(k>count){
            left = mid+1;
        }
        else if(k<count){
            ans = mid;
            right = mid-1;
        }
    }
    
    cout<<ans;
    
    return 0;
}

cs71107 5년 전 0

첫번째 질문만 답을 드리면, 1에서 k까지 모든 자연수가 적어도 한 번, 등장하기 때문입니다. 하지만 4같은 경우, 총 3번 등장하니까요 따라서 k번째 수가 k이하라는 것을 알 수 있습니다.

cs71107 5년 전 0

두 번째 같은 경우 n=3, k=8인 경우 mid값이 8으로 잡히면 8이 실제로 없음에도 정답을 8로 출력하게 되기 때문입니다.

doju 5년 전 6

@cs71107 잘못된 증명입니다. n = 2, k = 4일 때 3은 배열에 등장하지 않습니다.

이분탐색의 상한을 k로 잡아도 된다는 것은 모든 k에 대해 배열에 있는 수 중 k번째로 작은 수가 k 이하라는 뜻이며, 이는 모든 k에 대해 배열에 k 이하인 수가 k개 이상 존재한다는 것과 동치입니다.
배열의 각 줄을 순서대로 이어붙였을 때(ex. n = 3일 경우 1, 2, 3, 2, 4, 6, 3, 6, 9), 모든 k에 대해 앞의 k개의 수가 k 이하이므로 위의 명제가 성립합니다. 엄밀한 증명은 직접 해 보시기 바랍니다.

cs71107 5년 전 0

생각해보니 제가 실수를 했습니다.

제가 한 증명이 성립하면

두번째 의문점이 생길리 없지요.

지적해주신 doju님 감사합니다.

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

문제

문제

출처

ICPC

이분탐색으로 풀었지만 최대수와 if문에서 의문점이 남습니다.

kangbada0728 5년 전 0

cs71107 5년 전 0

cs71107 5년 전 0

cs71107 5년 전 0

doju 5년 전 6

cs71107 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말