아이디어를 찾는 난이도만으로 다이아몬드로 평가받은 문제이다. 필요한 알고리즘 지식이나, 구현의 난이도는 없다고 봐도 될 수준.
DP를 이용해서 푸는 방법이 떠오르지만, Ai의 범위가 너무 커서 쉽지 않다. dp[i][j][k] 를 i번째 공장에서까지 구입을 마쳤고, i번째 공장에서 살때 2개 묶음으로 산 갯수를 j개, 3개묶음으로 산 갯수를 k개인 상태에서의 최소가격으로 표현해서 이를 기반으로 점화식을 세울수 있지만, 테이블의 크기가 O(n*m*m)으로 최대 10^12 가 되어서 이 풀이는 무리이다.
관찰을 하면 공장 1개에서 사는 것보다, 공장 2개나 3개에서 묶어서 사는 것이 더 효율적이다. 앞에서부터 보면서 최대한 3개로 묶어서 사고, 안되는 경우 최대한 2개로 묶어서 사고, 나머지는 개별로 사는 그리디 풀이를 떠올릴수 있지만 이는 1 2 1 1 이라는 반례에 걸린다. (사실 이 반례를 찾는것이 쉽지 않았다)
조금 더 관찰을 해서 발견할수 있는 것은, 4개를 살 때 3개와 1개로 사는것과 2개와 2개로 사는 것의 가격이 똑같다는 것이다. 가격이 똑같다면 i번째 공장까지 2개묶음으로 산 경우가, i+1번째 공장에서 3개 묶음으로 확장시킬 여지가 있기 때문에, 3개 묶음으로 사는것보다 더 유리하다. 그래서 결국 최적 전략은, i-1번째 공장까지 1개묶음, 2개묶음, 3개묶음으로 산 것들에 대해서, i번째 공장에서는 제일먼저 1개묶음을 2개묶음으로 최대한 늘리고, 물건이 남으면 2개묶음을 3개묶음으로 늘리고, 그러고도 남는 물건들에 대해서는 그냥 1개묶음으로 사는 것이 된다.
시간복잡도는 O(n)이다.
-