책꽂이 만들기

책꽂이 만들기

 

제한시간: 1000 ms    메모리제한: 128 MB

 

지헌이는 책꽂이를 만들려고 한다. 

책꽂이의 설계도를 작성하고 보니 길이가 L1, L2, ..., LN(1≤Li≤50000)인 N(1≤N≤20000)개의 널빤지가 필요하다는 사실을 알았다. 

지헌이는 목재상에서 필요한 크기(L1+L2+...+LN)의 널빤지를 구입했으나 필요한 크기로 자르기 위해서는 톱이 필요했다.

 

지헌이는 아무리 찾아 보아도 톱이 없다는 것을 알고 절망에 빠졌다. 

이런 모습을 지켜보던 종현이는 지헌이에게 자신이 톱을 빌려줄테니 그 대가로 널빤지를 자를 때마다 그 널빤지의 길이만큼의 비용을 지불하라고 했다. 

예들 들어 길이가 10인 널빤지를 둘로 나누게 되면 10의 비용을 지불하라는 것이다.

 

지헌이는 자신의 어려움에 처해 있다는 것을 이용해서 돈을 벌려고 하는 종헌이가 얄밉기는 했지만 달리 방법이 없어 그렇게 하기로 했다.

 

지헌이는 비용을 최소화하기 위해 자르는 위치와 순서를 잘 결정해야만 한다. 

지헌이가 널빤지를 자르기 위해 필요한 최소한의 비용을 구하는 프로그램을 작성해 보자.

 

첫 번째 줄에 지헌이가 잘라야 하는 널빤지의 개수 N이 입력되고 이후 N개의 줄에 걸쳐 각 널빤지의 길이를 나타내는 정수가 입력된다.

 

지헌이가 종현이에게 지불해야하는 비용의 최소값을 출력한다.

 

3

8

5

8

 

34

 

 

 

아래와 같이 자르면 최소값이 된다. 길이가 21인 널빤지를 8과 13으로 자른다. (비용 21) 길이가 13인 널빤지를 5와 8로 자른다. (비용 13) 다른 어떠한 방법으로 잘라도 비용을 34보다 적게 들일 수는 없다.

 

#include <stdio.h>

#define MAX 7 // 20010

int N, hcnt;
long long heap[MAX]; // 널빤지의 개수

void Swap(long long &x, long long &y) { long long z = x; x = y; y = z; }

void push(int p)
{
	if (p <= 1 || heap[p / 2] <= heap[p]) return;
	Swap(heap[p / 2], heap[p]);
	push(p / 2);
}

void pop(int p)
{
	int np = p * 2;
	if (np > hcnt) return;
	if (np < hcnt && heap[np] > heap[np + 1]) np++;
	if (heap[p] <= heap[np]) return;
	Swap(heap[p], heap[np]);
	pop(np);
}

int main()
{
	freopen("input.txt", "r", stdin);
	long long ans = 0, tmp;
	scanf("%d", &N);
	hcnt = N;
	for (int i = 1; i <= N; i++) {
		scanf("%lld", &heap[i]);
		push(i);
	}
	while (hcnt > 1) {
		tmp = heap[1]; // 제일 작은 수 
		heap[1] = heap[hcnt--]; pop(1);
		tmp += heap[1]; // 다음으로 작은 수과 합
		heap[1] = heap[hcnt--]; pop(1);
		ans += tmp; // 정답 누적해 나감
		heap[++hcnt] = tmp; // 가장 작은 거 두ㅐ 더해서 힙에 넣기
		push(hcnt);
	}
	printf("%lld\n", ans);
	return 0;
}