MAX-SCORE (2009_1)

MAX-SCORE (2009_1)

대회 참가자들의 좋은 성적을 위해, 여러 개의 후보 문제중 대회 출제용으로 몇 개를 뽑으려 한다. N(1<=N<=1000)개의 문제 유형이 있다. 그리고 각 유형마다 그것을 풀때 얻는 점수와 푸는데 걸리는 시간이 주어지게 된다. 출제할 문제의 개수는 상관이 없으며, 원하는 유형의 문제를 적당한 개수로 출제하여(한 유형당 여러 문제 가능하며, 어떤 유형에서 문제가 출제되지 앟아도 된다.) 제한시간M(1<=M<=10000)안에 그 문제들을 다풀도록, 그러면서 얻는 점수는 최대가 되도록 프로그램을 작성하시오.

 

입력 설명

첫 째 줄에는 제한 시간 M과 문제 유형의개수 N이 입력

둘째 줄부터 N+1번째 줄에는 각각 문제 유형의 정보가 입력 그 유형의 문제를 풀었을 때의 점수와 그 문제를 푸는데 걸리는 시간이 입력

 

출력 설명

제한시간 안에 풀수 있도록 문제를 출제했을 때 얻을수 있는 최대 점수를 출력하시오.

 

입력예시

300 4

100 60

250 120

120 100

35 20

 

출력예시

605

소스

#include<stdio.h>
int count[16],m,n;
struct problem
{
 int point,cost;
}p[10],tmp;
void input()
{
 FILE *fp=fopen("input.txt","r");
 int i,j;

 fscanf(fp,"%d %d", &m, &n);
 for(i=1;i<=n;i++)
  fscanf(fp,"%d %d", &p[i].point, &p[i].cost);
 for(i=1;i<n;i++)
 {
  for(j=i+1;j<=n;j++)
  {
   if(p[i].cost > p[j].cost)
   {
    tmp=p[i];
    p[i]=p[j];
    p[j]=tmp;
   }
  }
 }
 fclose(fp);
}
void process()
{
 FILE *fp1=fopen("output.txt","w");
 int i,j;

 for(i=1;i<=m/20;i++)
 {
  for(j=1;j<=n;j++)
  {
   if(p[j].cost <= i*20)
   {
    if(count[i] <= count[i-(p[j].cost/20)]+p[j].point)
     count[i] = count[i-(p[j].cost/20)]+p[j].point;
   }
  }
 }
 fprintf(fp1,"%d", count[m/20]);
}
void main()
{
 input();
 process();
}