rlaalswo01   2년 전

풀이 과정 등을 보지 않고 풀어보려는데 내공이 부족해 고생 중이네요.


고민한 끝에 

1. 목적으로 하는 수퍼 파일을 만들기 위한 병합 과정에서 큰 파일을 포함한 병합 파일을
병합에 다시 사용할 때마다 큰 비용을 반복적으로 누적하는 효과가 발생한다.
2. 마지막 덩어리를 만들 때 두 개의 덩어리가 병합되며, 그 비용은 늘 모든 항의 크기의 합과 같다.
1 + 2. 병합이 완료된 마지막 덩어리를 만들기 전의 두 덩어리가 크지 않도록 한다.
(큰 것이 있다면 큰 것이 만들어지면서, 또 다시 그것이 최종 덩어리를 만드는데 사용되면서 큰 비용을 발생시킴)



결론. 
1. 두 개의 덩어리로 나눠질 때, 가장 균등한 두 덩어리로 나뉘어야 한다.
(한 쪽이 작아지면 한 쪽이 커짐.)
2. 나눈 양 조각을 계속 같은 방식으로 분해할 수 있다.
3. 분해하여 발생하는 두 조각의 크기의 합
=현재 덩어리를 만들 때 발생한 병합 비용
=현재 덩어리 크기

=> 큰 덩어리를 균등한 두 조각으로 분해하며 비용을 누적한다.

이런 아이디어로 진행했는데, 2번 예제 입력시 865가 나오네요.
한 끗 차이라, 제 아이디어가 전혀 틀린 아이디어인데 운이 좋게
정답에 가까운 수가 나왔을 뿐인건지, 아이디어는 맞는데 코드의 디테일이
틀린 건지 궁금합니다.

doju   2년 전

합이 비슷한 두 그룹으로 나눈다는 것은 좋은 발상이지만 최소 비용을 구하지는 못할 수 있습니다.

rlaalswo01   2년 전

뭔가 스스로 수학적인 의미를 찾아 해결하려 하다가 걍 쪼개면서

알아서 최솟값 반환하라는 식으로 하니 풀리네요 ㅎㅎ

허무하기도 하지만 뭔가 이게 진짜 DP의 미학이구나 싶었습니다.

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