[CODEGROUND] 재활용

#include <iostream> #include <fstream> #include <vector> #include <queue> #include <functional> #include <algorithm> #include <cmath> using namespace std; #define PAIR pair<int, pair<int,int> > int main() { int for_count, house_count, trash_count; cin >> for_count; for (int k = 1; k <= for_count; k++) { cin >> house_count >> trash_count; if (trash_count >= house_count) { cout << "Case #" << k << endl; cout << 0 << endl; continue; } vector<int>house; vector<pair<int, int> > section; priority_queue<PAIR>distance; int input; for (int j = 0; j < house_count; j++) { cin >> input; house.push_back(input); } sort(house.begin(), house.end()); for (int j = 0; j < house_count - 1; j++) distance.push(make_pair(house[j + 1] - house[j], make_pair(j, j + 1))); trash_count--; while (trash_count--) { section.push_back(make_pair(distance.top().second.first, distance.top().second.second)); distance.pop(); } sort(section.begin(), section.end()); int result = 0, start = 0, end; while (1) { if (section.empty()) end = house_count - 1; else end = section[0].first; int mid = (start + end) / 2; for (int j = start; j <= end; j++) result += abs(house[mid] - house[j]); if (section.empty()) break; start = section[0].second; section.erase(section.begin()); } cout << "Case #" << k << endl; cout << result << endl; } }

맨 처음엔 priority_queue에 거리를 저장한 후

trash can의 수보다 1개 적게 pop하면서 구간을 나누었고

구간에서 최소의 거리를 구하는 방법

즉 시작과 끝의 index를 더하고 2로 나눈 값을 기준으로 거리를 계산하였는데

안돌아간다.

내머리로는..아직..예외를 못찾겠다..

보통 codeground의 중급 normal은 거의 DP라고 보면 된다.

이것도 DP였다.

제발 DP..하..계속 공부하자

예진이가 DP는 아니 문해기는 많이 풀어봐야한다고 했다.

더풀어보고 코드를 분석해보면

어느순간 나도 알게되게찌..8_8

공유하기 코드를 보고 풀어보았다.

#include <iostream> #include <fstream> #include <vector> #include <cmath> #include <algorithm> using namespace std; #define MAX_INT 1e18 int house_count; vector<vector<long long> > pre_distance, cache; long long DP(int index, int remain) { if (index == house_count) { cache[index][remain] = 0; return 0; } if (remain == 0) { cache[index][remain] = MAX_INT; return MAX_INT; } long long&ret = cache[index][remain]; if (ret != -1) return ret; ret = MAX_INT; for (int j = index; j < house_count; j++) ret = min(ret, pre_distance[index][j] + DP(j + 1, remain - 1)); return ret; } int main() { int for_count, trash_count; cin >> for_count; for (int i = 1; i <= for_count; i++) { cin >> house_count >> trash_count; vector<int>house = vector<int>(house_count, 0); pre_distance = vector<vector<long long> >(house_count, vector<long long>(house_count, 0)); cache = vector<vector<long long> >(house_count + 1, vector<long long>(trash_count + 1, -1)); for (int j = 0; j < house_count; j++) cin >> house[j]; sort(house.begin(), house.end()); //start부터 end까지 모든 경우의 수를 미리 저장해놓는다. for (int start = 0; start < house_count; start++) { for (int end = start; end < house_count; end++) { int mid = (start + end) / 2; for (int index = start; index <= end; index++) pre_distance[start][end] += abs(house[mid] - house[index]); } } cout << "Case #" << i << endl; cout << DP(0, trash_count) << endl; } }

와..DP는 이렇게 푸는거구나..깨달았다

DP문제를 훨씬더 많이 풀어봐야겠다..

이코드를 분석해보면서 풀어보자

일단 cache의 index는 시작하는 index와 남은 trash can의 개수이다

1부터 1까지 해본후 2부터 돌려본다

이렇게 모든 경우를 돌려보지만

만약 trash can의 개수가 2개가 남았을 때 3으로 시작하는 것을 돌려보았다면

미리 저장되어있어 다시 돌려보지 않아도 된다.