백준 : 8980번, 택배

문제 주소 : https://www.acmicpc.net/problem/8980

정답 비율 : 36.326% (2021.06.27 14:14 기준)

8980번: 택배

 

문제 풀이 :

문제의 조건 2(트럭은 지나온 마을을 되돌아가지 않습니다.)에 따르면 각 마을에 경유할 수 있는 물자의 양은 트럭의 최대 용량과 같습니다. 물자의 양이 트럭의 최대 용량을 초과했다는 의미는 지나온 마을을 되돌아가서 다시 물자를 실었다는 이야기가 됩니다.

 

따라서 마을 1에서 마을 3으로 10개의 박스를 보낸다고(1 3 10 인 데이터에 대하여) 하면 마을 1과 마을 2에서 경유할 수 있는 물자의 양인 10을 소모하게 됩니다. 

 

이를 바탕으로 목적지를 기준으로 데이터를 오름차순으로 정렬해야 합니다.

 

그 이유는 a b c라는 데이터에 대하여 해당 데이터를 선택했을 때 마을 a에서 마을 b-1까지 경유할 수 있는 물자의 양에 영향을 끼치지만 마을 b+1 이상의 마을에 대해서는 경유하는 물자의 양에 어떠한 영향을 주지 않습니다.

 

따라서 오름차순으로 정렬을 해야 그리디의 탐욕스러운 선택 조건(greedy choice property)에 만족합니다.

 

*** 목적지가 같을 때 출발지 기준으로 정렬이 필요하지 않은 이유 *** 

마을 b에 배달될 수 있는 물자의 양은 마을 b-1에 경유할 수 있는 물자의 량에 의해 최댓값이 결정되어있기 때문입니다. 따라서 출발지는 중요하지 않습니다. 단지 목적지가 b인 해당 데이터의 선택 가능 여부만 확인하면 됩니다.

 

 

코드는 다음과 같습니다.

 

C99

// solve 8980
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _infor {
	int s;
	int e;
	int v;
}INFOR;

INFOR infor[10000];
int les[2000];			//경유할 수 있는 물자의 양

int compare(const void* a, const void* b) {
	INFOR *v1 = (INFOR*)a;
	INFOR *v2 = (INFOR*)b;

	return v1->e > v2->e;
}

int main(void) {
	int node = -1, max_w = -1, count = 0, ans = 0;
	scanf("%d %d", &node, &max_w);
	scanf("%d", &count);

	for (int i = 0; i < count; i++)
		scanf("%d %d %d", &infor[i].s, &infor[i].e, &infor[i].v);

	qsort(infor, count, sizeof(INFOR), compare);

	for (int i = 1; i < node; i++)
		les[i] = max_w;

	for (int i = 0; i < count; i++) {
		int min = 10001;

		for (int j = infor[i].s; j < infor[i].e; j++)
			min = min > les[j] ? les[j] : min;

		if (infor[i].v > min) {
			ans += min;
		}
		else {
			ans += infor[i].v;
			min = infor[i].v;
		}

		for (int j = infor[i].s; j < infor[i].e; j++)
			les[j] -= min;
	}
	
	printf("%d", ans);

	return 0;
}

-> qsort 첨 써보는데 엄청 편하네요. 이걸 모르고 살았다니 ㅠㅠ

 

qsort : compare함수 간단 정리

오른차순

a > b : return 1a = b : return 0a < b : return -1

내림차순

a > b : return -1

a = b : return 0

a < b : return 1