[코드업] 3321 : 최고의 피자 (C)

알고리즘

그리디

힌트

가장 칼로리가 높은 토핑만 생각한다.

풀이

도우는 무조건 포함해야 하므로 cost(가격)와 cal(칼로리)를 도우의 가격과 칼로리로 초기화해준다.

토핑의 가격들이 입력되면 내림차순으로 정렬해준다.

(토핑은 한 번만 사용할 수 있으므로 남아 있는 토핑 중 가장 칼로리가 높은 토핑만 고려하면 된다.)

현재의 칼로리/달러가 i번째 토핑을 추가했을 때의 칼로리/달러보다 클 경우 cal과 cost를 갱신해준다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

#include<iostream> #include<algorithm> using namespace std;   int cmp(int a, int b){     return a>b?1:0; }   int main(){     int n,A,B,C;     int in[100];          cin>>n;     cin>>A;     cin>>B;     cin>>C;          int cost=A, cal=C;          for(int i=0;i<n;i++){         cin>>in[i];     }          sort(in,in+n,cmp);          for(int i=0;i<n;i++){         if((float)cal/cost<(float)(cal+in[i])/(cost+B)){             cal+=in[i];             cost+=B;         }     }          cout<<cal/cost;      }