글 읽기 - 나무 자르기 시간 초과 관련 질문 [c언어]

ttangle1234 1년 전 1

웬만한 반례 10개는 넘게 넣어본 거 같은데 다 맞게 나옵니다 ㅜ-ㅜ

finder 함수 내에 무한루프를 돌지 않도록 설정을 해보았는데, 왜 시간 초과가 뜨는지 잘 모르겠습니다.

단순히 시간복잡도가 높아서 그런 걸까요?

반례나 첨언 부탁드립니다. 감사합니다.

#include <stdio.h>
#include <stdlib.h> 
int result, j = 1, m, trees[1000000];

int compare(const void *a, const void *b);
int finder(int x, int y);

int main() {
    int n, h;
    long long sum = 0;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) {
        scanf("%d", &trees[i]);
    }

    qsort(trees, n, sizeof(int), compare);
    /*for (int i = 0; i < n; i++) {
        printf("%d ", trees[i]);
    }
    printf("\n");*/

    while(1) {
        h = trees[j];
        for (int i = 0; i < j; i++) {
            sum += trees[i] - h;
        }
        if (sum >= m) break;
        j++;
        sum = 0;
    }
    
    finder(trees[j - 1], trees[j]);

    printf("%d", result);
    return 0;
}

int finder(int x, int y) {
    int mid;
    long long sum = 0;
    mid = (x + y) / 2;
    for (int i = 0; i < j; i++) {
        sum += trees[i] - mid;
    }
    //printf("\nx=%d y=%d j=%d m=%d mid=%d sum=%d", x, y, j, m, mid, sum);
    if(sum < m && sum > m - j) result = mid - 1;
    else if(sum > m && sum < m + j || sum == m) result = mid;
    else if(sum < m) {
        if(mid==x || mid==y) return -1;
        finder(mid, y);
    }
    else {
        if(mid==x || mid==y) return -1;
        finder(x, mid);
    }
}

int compare(const void *a, const void *b) {
    int num1 = *(int *)a;  
    int num2 = *(int *)b;   

    if (num1 < num2)  
        return 1;    
    
    if (num1 > num2)    
        return -1;       
    
    return 0; 
}

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

문제

문제

출처

ICPC

나무 자르기 시간 초과 관련 질문 [c언어]

ttangle1234 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말