More actions
소감
단순히 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)
이 알고리즘은 답을 산출해 내지 못한다.
//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
//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;
}