반응형
https://algospot.com/judge/problem/read/BOOKSTORE
algospot.com :: BOOKSTORE
인터넷 서점 문제 정보 문제 새 학기가 시작되면 항상 부담되는 것이 비싼 교과서 가격이다. 오랜 병특 생활을 마치고 복학한 스탱은 이번 학기에 사야 하는 N 권의 교과서를 인터넷 서점에서 사
algospot.com
아래 케이스를 생각하지 못했음.
1
2 1
6000 5000
1000 0
정답은 6000원임.
현재 가격에서 마일리지를 차감하여 계산한 방식으로는 2000원이므로 오답임.
구매한 책의 마일리지를 다음 책에서 모두 사용할 수 없는 경우를 생각해야함.
#include
typedef struct{
int price, point;
}_ds;
_ds MAP[201][101];
int N, M;
void sort()
{
for (int k = 0; k < M; k++)
for (int i = 0; i < N; i++)
for (int j = i+1; j < N; j++)
if (MAP[i][k].point < MAP[j][k].point)
{
_ds temp = MAP[i][k];
MAP[i][k] = MAP[j][k];
MAP[j][k] = temp;
}
}
int solve()
{
int Small = 9999999;
for (int i = 0; i < M; i++){
int _count = MAP[0][i].price, _point = MAP[0][i].point;
for (int j = 1; j < N; j++)
if (_point < MAP[j][i].price)
{
_count += (MAP[j][i].price - _point);
_point = MAP[j][i].point;
}
else
{
_point += -MAP[j][i].price + MAP[j][i].point;
}
if (Small > _count)
Small = _count;
}
return Small;
}
int main()
{
int C;
for (scanf("%d", &C); C > 0; C--)
{
scanf("%d %d", &N, &M);
for (int i = 0; i < N;i++)
for (int j = 0; j < M; j++)
scanf("%d %d", &MAP[i][j].price, &MAP[i][j].point);
sort();
printf("%d\n", solve());
}
return 0;
}반응형