== 소감 ==
단순히 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;
}
}}}
== 나한테 할 말 ==
----
[IsBiggerSmarter?] [AOI]