글 읽기 - 파일 합치기 질문입니다(스포있음)

kettlebell 6년 전 0

DP 문제로 알고 풀려고 했는데, 예전에 비슷한 문제를 그리디하게 풀어본 적이 있어서 priority_queue에 넣고 값을 계산했더니 2번째 테스트 케이스에서 훨씬 적은 답이 나옵니다.

분명 제가 문제를 잘못 이해한 것 같은데, 어떤 부분을 잘못 이해했는지 설명 부탁드립니다.

int minCost()
{
    priority_queue<int> pq;
    int cost = 0;
    while(sz(pq) > 1)
    {
        int a = -pq.top(); pq.pop();
        int b = -pq.top(); pq.pop();
        cost += a + b;
        pq.push(-(a + b));
    }
    return cost;
}

jh05013 6년 전 2

1715번 (카드 정렬하기) 문제와 달리 파일 합치기에서는 인접한 파일만 합칠 수 있습니다.

kettlebell 6년 전 0

명확히 해 주셔서 감사합니다.

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

문제

문제

출처

ICPC

파일 합치기 질문입니다(스포있음)

kettlebell 6년 전 0

jh05013 6년 전 2

kettlebell 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말