소감 ¶
단순히 Greedy 알고리즘으로 접근. 실패. Dynamic Programming 이 필요함을 테스트 케이스로써 확인했다. Dynamic Programming 을 실제로 해본 경험이 없기 때문에 감이 잡히지 않았다. Introduction To Algorithm에서 Dynamic Programing 부분을 읽어 공부한 후 문제분석을 다시 시도했다. 이 문제를 쉽게 풀기 위해 Weight를 정렬한 배열과 IQ를 정렬한 배열을 하나의 문자열로 보았다. 그렇다면 문제에서 원하는 "가장 긴 시퀀스" 는 Longest Common Subsequence가 되고, LCS는 Dynamic Algorithm으로 쉽게 풀리는 문제중 하나였다. 무게가 같거나, IQ가 같을수도 있기 때문에 LCS에서 오류가 나는 것을 피하기 위해 소트함수를 처리해 주는 과정에서 약간의 어려움을 겪었다.
{{| 2005/07/09 Accepted 0:00.035 64 |}}
lcs_length함수에서 cost table을 만들어주는 과정의 running time은 O(n*n), memory cost는 O(n*n)이다. 그리고 print_lcs 함수에서 longest path를 거슬러 올라가는 running time은 O(n + n) = O(n)이다.
무엇보다 몇일동안 고생해서 푼 보람이 있어 좋다.
코드 ¶
ver1 (Greedy Algorithm) ¶
이 알고리즘은 답을 산출해 내지 못한다.
~cpp //no 10131 #include <fstream> #include <vector> #include <algorithm> #include <iostream> using namespace std; fstream fin("input.txt"); const int MAX_ELEPHANT = 1100; struct Elephant { int index; int weight; int IQ; bool operator () (const Elephant & a, const Elephant & b) { if (a.weight < b.weight) return true; else if (a.weight == b.weight) { if (a.IQ > b.IQ) return true; } return false; } }; int input_elephant_info(Elephant * e); void count_elephant(Elephant * elephant, int num_elephant); int main() { Elephant elephant[MAX_ELEPHANT]; int num_elephant = input_elephant_info(elephant); sort(&elephant[0], &elephant[num_elephant], Elephant()); count_elephant(elephant, num_elephant); return 0; } int input_elephant_info(Elephant * e) { int count = 0; while (fin >> e[count].weight >> e[count].IQ) { e[count].index = count + 1; count++; fin.get(); if (fin.peek() == EOF) break; } return count; } void count_elephant(Elephant * e, int num) { // test // for (int t = 0; t < num; t++) // { // cout << e[t].index << " " << e[t].weight << " " << e[t].IQ << endl; // } // end int max_count = 0; int count; vector<int> v_temp; vector<int> result; result.reserve(MAX_ELEPHANT); v_temp.reserve(MAX_ELEPHANT); Elephant temp; int i; for (int k = 0; k < num - 1; k++) { temp.weight = e[k].weight; temp.IQ = e[k].IQ; v_temp.push_back(e[k].index); count = 1; for (i = k + 1; i < num; i++) { if (temp.weight >= e[i].weight || temp.IQ <= e[i].IQ) continue; temp.weight = e[i].weight; temp.IQ = e[i].IQ; count++; v_temp.push_back(e[i].index); } if (count > max_count) { max_count = count; result = v_temp; } v_temp.clear(); } cout << max_count << endl; for (i = 0; i < max_count; i++) cout << result[i] << endl; }
ver2. Dynamic Algorithm ¶
~cpp //no 10131 #include <vector> #include <algorithm> #include <iostream> using namespace std; const int MAX_ELEPHANT = 1010; const int WEIGHT = 1; const int IQ = 2; int TYPE_SORT; struct Elephant { short index; short weight; short IQ; bool operator () (const Elephant & a, const Elephant & b) { if (TYPE_SORT == WEIGHT) { if (a.weight < b.weight) return true; else if (a.weight == b.weight && a.IQ <= b.IQ) return true; return false; } else { if (a.IQ > b.IQ) return true; else if (a.IQ == b.IQ && a.weight > b.weight) return true; return false; } } }; Elephant elephant_weight[MAX_ELEPHANT]; Elephant elephant_IQ[MAX_ELEPHANT]; int num_elephant; vector <int> result; int input_elephant_info(); void sort_elephant(); int lcs_length(unsigned char t[][MAX_ELEPHANT]); void print_lcs(int i, int j, unsigned char t[][MAX_ELEPHANT]); void print_route(int len); int main() { unsigned char table[MAX_ELEPHANT][MAX_ELEPHANT]; num_elephant = input_elephant_info(); sort_elephant(); int len = lcs_length(table); print_lcs(num_elephant, num_elephant, table); print_route(len); return 0; } int input_elephant_info() { int count = 0; while (cin.peek() != EOF) { count++; cin >> elephant_weight[count].weight >> elephant_weight[count].IQ; elephant_weight[count].index = count; elephant_IQ[count] = elephant_weight[count]; cin.get(); } return count; } void sort_elephant() { TYPE_SORT = WEIGHT; sort(&elephant_weight[1], &elephant_weight[num_elephant+1], Elephant()); TYPE_SORT = IQ; sort(&elephant_IQ[1], &elephant_IQ[num_elephant+1], Elephant()); } int lcs_length(unsigned char t[][MAX_ELEPHANT]) { int i, j; for (i = 0; i <= num_elephant; i++) t[0][i] = t[i][0] = 0; for (i = 1; i <= num_elephant; i++) { for (j = 1; j <= num_elephant; j++) { if (elephant_weight[i].index == elephant_IQ[j].index) t[i][j] = t[i-1][j-1] + 1; else if (t[i-1][j] >= t[i][j-1]) t[i][j] = t[i-1][j]; else t[i][j] = t[i][j-1]; } } return t[i-1][j-1]; } void print_lcs(int i, int j, unsigned char t[][MAX_ELEPHANT]) { if (i == 0 || j == 0) return; if (elephant_weight[i].index == elephant_IQ[j].index) { print_lcs(i-1, j-1, t); result.push_back(elephant_weight[i].index); } else if (t[i-1][j] >= t[i][j-1]) print_lcs(i-1, j, t); else print_lcs(i, j-1, t); } void print_route(int len) { cout << len << endl; for (int i = 0; i < len; i++) cout << result[i] << endl; }