각각 a1, a2, ..., an (a1<=a2<= ... <=an) 개의 카드로 이뤄진 카드 묶음이 n개 있다.
이들을 총 하나의 카드 묶음으로 합치려고 한다. 두 묶음을 하나의 묶음으로 합치는 과정을 반복하는 방식으로 수행한다.
보유 카드 개수가 각각 a, b개인 두 묶음을 하나로 합치려면 a+b 번의 비교가 필요하다.
예를 들어, 10장, 20장, 40장의 카드로 이뤄진 묶음 3개가 있다면,
10장과 20장을 먼저 합치고 40장을 나중에 합치면 (10+20)+((10+20)+40)=100번의 비교가 필요하다.
그러나 만약 10장과 40장을 먼저 합치고 20장을 나중에 합치면 (10+40)+((10+40)+20)=120번의 비교가 필요하다.
이때 다음을 증명하시오 :
항상 현재 상태에서 1번째, 2번째로 적은 카드를 포함하는 묶음끼리 합치는 것을 반복할 때가 최소 비교 횟수를 가진다.
(1번째, 2번째로 적은 카드를 포함하는 묶음이 무엇인지 알기 위해서는 비교가 필요 없다고 가정함.)
문제 출처는 백준 1715번
그 행렬곱 dp랑 똑같이 하면 되지않나
a1, a2, ..., an의 대소관계가 정해지지 않은 상태에서 a1, a2를 합치고, 이를 a3와 합치고, 이를 a4와 합치고, ..., an까지 합쳤을 때 총 비교횟수는 (n-1)(a1+a2)+(n-2)a3+(n-3)a4+ ... + 1×an 이니까, 이를 최소가 되게 조건은 a1<=a2<=a3<=...<=an 일 듯? (a1<=a2은 그냥 뭐...)
신박한 증명 찾아낸거같은데 내일써야겠다
그냥 '재배열부등식' 문제 아닌가
귀납가설 세우는데 애먹었다. '묶음개수가 n이하일때 항상 최소루트는 a1+a2를 포함한다면' 으로 하면 안됨. 3 3 5 5 라든지 2 3 5 5 같은 경우는 a1+a4로 시작해도 되기 때문. 아마도 '묶음개수가 n이하일때 항상 a1+a2는 최소루트를 막지 않는다면' 이라고 해야할 듯함