2006 한국정보올림피아드 KOI 고등부 1번 기지국(BOJ: 2300) 풀이

 

x좌표 기준으로 정렬합니다.

dp[4] = (4를 위한 cost) + (1~3의 최적Cost)

dp[4] = min(dp[4] , (3~4 Cost) + (1~2의 최적Cost) )

dp[4] = min(dp[4] , (2~4 Cost) + (1을 위한 Cost) )

dp[4] = min(dp[4] , (1~4 Cost) )

 

구간의 cost를 구하는 방법

Max(A~B사이의 X축거리 , A~B사이의 모든 건물 중 Y절대값이 가장 큰 값 * 2) 

#include  <stdio.h>
#include <math.h>
#include <stdlib.h>
long long d[10005];


typedef struct point {
	long long x, y;
}Point;
struct point pointList[10000];
int comp(const void* p1, const  void* p2) {
	return ((Point*)p1)->x - ((Point*)p2)->x;
}

int main() {

	int N;
	//freopen("Text.txt", "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &pointList[i].x);
		scanf("%lld", &pointList[i].y);
	}
	qsort(pointList, N, sizeof(Point), comp);
	d[0] = abs(pointList[0].y) * 2;

	for (int i = 1; i < N; i++) {
		d[i] = d[i - 1] + abs(pointList[i].y) * 2;
		long long maxHeight = 0;
		for (int j = i-1; j >=0 ; j--) {			
			long long height = abs(pointList[i].y) > abs(pointList[j].y) ? abs(pointList[i].y) * 2 : abs(pointList[j].y) * 2;
			if (maxHeight < height) {
				maxHeight = height;
			}
			else {
				height = maxHeight;
			}
			long long width = pointList[i].x - pointList[j].x;
			long long cost;
			if (j > 0) {
				cost = d[j - 1] + (height > width ? height : width);
			}
			else {
				cost = (height > width ? height : width);
			}
			d[i] = d[i] < cost ? d[i] : cost;
		}
	}
	printf("%lld\n", d[N - 1]);


	return 0;
}