글 읽기 - 처음으로 이진탐색을 적용해보았습니다.

han030425 1년 전 0

기존의 for 반복문은 시간초과가 나서 이진탐색이라는 새로운 방법을 적용해보았습니다.

틀렸다고는 하는데 무엇이 문제일까요? 아무리 봐도 이진탐색 부분이 문제인것 같은데 처음 적용해보는거라 감을 도저히 못 잡겠습니다...ㅠㅠㅠ

#include <stdio.h>

int main()
{
    int N, M, i, j=0, val, highest=0, sum=0, count=0;
    scanf("%d %d", &N, &M);
    int tree_number[N];
    int britz[200]={0};
    
    for (i=0; i<N; i++) {
        scanf("%d",&val);
        tree_number[i]=val;
        if (val>highest) {
            highest=val;
        }
    }
    
    printf("highest: %d\n",highest);
    
    // --- 이진탐색 시작 --- //
    int low=0, high=highest, mid;
    while (low<=high) {
        sum=0;
        mid = (low+high)/2;
        for (i=0; i<N; i++) {
            if (tree_number[i]>=mid) {
                sum+=tree_number[i]-mid;
            }
        }
        printf("sum: %d, low: %d, high: %d, mid: %d, M: %d\n",sum, low, high, mid, M);
        if (sum==M) {
            printf("%d\n",mid);
            return 0;
        }
        else if (sum<M) {
            high=mid-1;
        }
        else if (sum>M) {
            britz[count]=mid;
            count++;
            low=mid+1;
        }
    }
    
    // -- 일치하는 값이 나오지 않은 경우 -- //
    
    j=britz[0];
    
    for (i=1; i<200; i++) {
        if (britz[i]==0) {
            break;
        }
        else if (britz[i]<j) {
            j=britz[i];
        }
    }
    
    printf("%d\n",j);
    
    return 0;
}

seawon0808 1년 전 0

예제부터 넣어보세요.

han030425 1년 전 0

예제는 다 잘 나옵니다... 혹시 반례를 아신다면 알려주시면 감사하겠습니다ㅠㅠ

seawon0808 1년 전 0

출력 형식을 다시 확인해 보세요.

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

문제

문제

출처

ICPC

처음으로 이진탐색을 적용해보았습니다.

han030425 1년 전 0

seawon0808 1년 전 0

han030425 1년 전 0

seawon0808 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말