imported>Unknown at 05:28, 7 February 2021

2021-02-07T05:28:24Z

New page

==== 소감 ====
2005-12-27 Accepted 2.184 528
동적프로그래밍 문제. n! 번의 수행을 해야하는 문제가 동적프로그래밍을 이용하니 O(n^2)만에 풀 수 있다. 동적프로그래밍의 힘이 대단하다.
==== 코드 ====
// 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]] [[문보창]]

WeightsAndMeasures/문보창 - Revision history

imported>Unknown at 05:28, 7 February 2021