티스토리 뷰
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();
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
이 글 이전 시간의 글들은 모두 예전 블로그의 포스트들입니다. (0) | 2011.02.25 |
---|---|
최대공통부분 수열 (0) | 2011.02.25 |
동전교환 (0) | 2011.02.25 |
UVA 231 캐쳐 미사일 검사 (0) | 2011.02.25 |
웜 바이러스 (0) | 2011.02.25 |
- Total
- Today
- Yesterday