안녕하세요,
재재입니다.
BOJ 13975 파일 합치기 3 문제 풀이입니다.
BOJ 13975 파일 합치기 3
(1) 문제 설명
출처 : https://www.acmicpc.net/problem/13975
파일의 사이즈가 각각 들어오며,
인접한 두 파일을 합칠 때 비용은 두 파일의 사이즈를 더한 값입니다.
이런식으로 최선의 전략으로 파일을 하나로 만들어줬을 때,
그 비용의 최솟값을 구해주세요.
(2) 풀이 도출
임의의 2개를 합치는 과정에서 비용이 발생하는 구조입니다.
더해진 합의 비용이 적을수록 이득입니다.
항상 가장 작은 2개를 선택하여 값을 합해주면 됩니다.
이때, 적당한 자료구조로는 balanced 구조인 heap 만으로도 충분합니다.
가장 간단한 형태로 구현하고자 한다면,
max heap 을 사용하고, -를 곱해서 가장 큰 두개의 값을 선택해줘도 충분합니다.
(3) 정답 코드
BOJ 13975 파일 합치기 3