KOI(한국정보올림피아드) 2006년 고등부1번,중등부2번 기지국

https://www.acmicpc.net/problem/2300

#include <cstdio> #include <algorithm> using namespace std; #define MAX_N 10001 //O(N^2)에 돌려야 함. #define MAX_INT 987654321 int N; int D[MAX_N+1]; // D[1]부터 시작. struct Point { int x, y; bool operator<(const Point &p) const { return x < p.x; } //x로 정렬 }p[MAX_N]; void solve() { sort(p+1, p+N+1); //x좌표 순으로 정렬위함. D[0] = 0; //base case for(int i=1; i<=N; i++) { D[i] = MAX_INT; int height = 0; for(int j=i; j>=1; j--) { int width = p[i].x - p[j].x; height = max(height, p[j].y); int cost = max(width, height); D[i] = min(D[i], D[j-1] + cost); // D[i]와 (1부터 j-1까지의 기지국 처리 비용+j부터 i까지의 기지국 처리비용)을 비교한다. } } printf("%d", D[N]); } int main() { //Dynamic Programming scanf("%d", &N); for(int i=1; i<=N; i++) { scanf("%d %d", &p[i].x, &p[i].y); p[i].y = 2*abs(p[i].y); //정사각형이므로 절댓값을 씌워준 후 2배를 한다. } solve(); return 0; }