==== 소감 ====
2005-12-27  Accepted  2.184  528 
동적프로그래밍 문제. n! 번의 수행을 해야하는 문제가 동적프로그래밍을 이용하니 O(n^2)만에 풀 수 있다. 동적프로그래밍의 힘이 대단하다.
==== 코드 ====
{{{~cpp
// 10154 - Weights and Measures
#include <iostream>
#include <algorithm>
using namespace std;

//#include <fstream>
//fstream fin("in.txt");

#define MAX_SIZE 5608
#define MAX_WEIGHT 10000000

typedef struct
{
	int weight;
	int strength;
}Turtle;

inline
bool turtleGreater(const Turtle& A, const Turtle& B)
{
	return A.strength < B.strength;
}

void input(Turtle* t, int* numT)
{
	*numT = 1;
	while (cin >> t[*numT].weight >> t[*numT].strength)
		(*numT)++;
	(*numT)--;
}

void process(Turtle* t, int numT)
{
	int i, j;
	int dynamic[2][MAX_SIZE];
	int result;

	sort(&t[1], &t[numT+1], turtleGreater);

	for (i = 1; i <= numT; i++)
		dynamic[1][i] = MAX_WEIGHT;
	if (t[1].weight <= t[1].strength)
	{
		dynamic[1][1] = t[1].weight;
	}
	dynamic[1][0] = 0, dynamic[0][0] = 0;
	
	for (i = 2; i <= numT; i++)
	{
		for (j = 0; j <= numT; j++)
		{
			dynamic[i%2][j] = dynamic[(i-1)%2][j];
			if (j != 0 && dynamic[(i-1)%2][j-1] + t[i].weight < dynamic[(i-1)%2][j] && 
				dynamic[(i-1)%2][j-1] + t[i].weight <= t[i].strength)
				dynamic[i%2][j] = dynamic[(i-1)%2][j-1] + t[i].weight;
		}
	}

	for (i = numT; i >= 1; i--)
	{
		if (dynamic[numT%2][i] < MAX_WEIGHT)
		{
			result = i;
			break;
		}
	}

	cout << result << endl;
}

int main()
{
	Turtle turtle[MAX_SIZE];
	int numTurtle;
	input(turtle, &numTurtle);
	process(turtle, numTurtle);
	return 0;
}
}}}
----
[WeightsAndMeasures] [문보창]