=== 그리디로 === {{{~cpp // 10201 - Adventures in Moving: Part IV #include using namespace std; #define MAX_OIL 200 #define MAX_SIZE 103 #define MAX_NUM 1000000000 typedef struct { int length; int price; }Station; static int totalLength; /* 워털루에서 대도시까지의 거리 */ static int numStation; /* 주유소 수 */ static Station station[MAX_SIZE]; /* 주유소 정보 */ inline int getDistance(int i) { return station[i].length - station[i-1].length; } void input() { cin >> totalLength; totalLength += 100; cin.get(); numStation = 1; station[numStation].length = 0; station[numStation].price = 0; while (cin.peek() != EOF && cin.peek() != '\n') { numStation++; cin >> station[numStation].length >> station[numStation].price; cin.get(); } cin.get(); numStation++; station[numStation].length = totalLength; station[numStation].price = 0; } void process() { int maxmin, maxminprice , now = 1, tank = 100, go = 100, search = 2, cost = 0; while(now != numStation) { maxmin = 0; maxminprice = 1000000; while(station[now].length + go >= station[search].length) { // 서치의 가격이 작거나 같을때 if(station[now].price > station[search].price) { if(station[search].length - station[now].length >= tank) { cost += (station[search].length - station[now].length - tank)*station[now].price; tank = 0; } else tank = tank - station[search].length + station[now].length; now = search++; maxmin = 0; break; } // 서치의 가격이 클때 else { if(maxminprice > station[search].price) { maxmin = search; maxminprice = station[search].price; } search++; } } // 작은게 없을때 if(now + 1 == search && station[now].length + go < station[search].length) { cout << "Impossible\n"; return; } if(maxmin) { if(station[maxmin].length - station[now].length >= tank) { cost += (200 - tank)*station[now].price; tank = go - station[maxmin].length + station[now].length; } else tank = tank - station[maxmin].length + station[now].length; now = maxmin; search = now +1; } go = 200; } cout << cost << endl; } int main() { int numCase; cin >> numCase; cin.get(), cin.get(); for (int i = 0; i < numCase; i++) { input(); process(); if (i != numCase - 1) cout << endl; } return 0; } }}}