글 읽기 - 사용한 알고리즘까지 동일한데 왜 제출하면 바로 틀렸다고 나올까요?

kimjea1999 1년 전 0

우선순위 큐 사용하였고, 정수 범위 고려하여 long long으로 선언했습니다. 대체 왜 틀렸다고 하는지가 궁금합니다. 반례 알고 계신 분 있으시다면 부탁드립니다.

#include <stdio.h>

long long cards[1000] = {0};
int n, t;

long long heap[1000] = {0};
int heap_size = 0;

void insert(long long item){
    int i = ++heap_size;

    while((i != 1) && (item < heap[i/2])){
        heap[i] = heap[i/2];
        i /= 2;
    }

    heap[i] = item;
}

long long pop(void){
    long long item = heap[1];
    long long tmp = heap[heap_size--];
    int parent = 1, child = 2;

    while((child <= heap_size)){
        if(child < heap_size && heap[child] > heap[child+1]) child += 1;
        if(tmp <= heap[child]) break;
        heap[parent] = heap[child];
        parent = child;
        child *= 2;
    }
    heap[parent] = tmp;
    return item;
}

int main(int argc, char *argv[]){
    long long tmp;

    scanf("%d %d", &n, &t);
    for(int i=0; i<n; i++){
        scanf("%lld", &cards[i]);
        insert(cards[i]);
    }

    for(int i=0; i<t; i++){
        tmp = pop() + pop();
        insert(tmp);
        insert(tmp);
    }

    tmp = 0;
    for(int i=1; i<=heap_size; i++) tmp += heap[i];

    printf("%lld\n", tmp);

    return 0;
}

yhj1937 1년 전 1

n이 최대 1000인데 heap이 1부터 시작해서 범위 문제가 생기는 것 같습니다.

kimjea1999 1년 전 0

yhj1937님// 아이고야... 부끄럽게도 말씀해주시기 전까지는 조금도 눈치채지 못하고 있었네요 ^^; 질문 글 읽어주시고 답변 달아주셔서 감사합니다. 덕분에 편히 잠들 수 있겠습니다 ㅎㅎ

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

문제

문제

출처

ICPC

사용한 알고리즘까지 동일한데 왜 제출하면 바로 틀렸다고 나올까요?

kimjea1999 1년 전 0

yhj1937 1년 전 1

kimjea1999 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말