5545번 최고의 피자 | Baekjoon BOJ 백준 5545 C++ 코드, 해설, 풀이

 

 

 

이번 포스팅은 백준 5545번 최고의 피자입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/5545

5545번: 최고의 피자

 

 

 

기본 알고리즘

그리디 알고리즘

 

참고

line 22
열량 높은 순으로 토핑 내림차순 정렬

line 30-36
토핑을 1개씩 추가할 때마다 1원 당 열량을 구하고 기존의 1원 당 열량보다 크면 1원 당 열량 갱신

 

 

 

전체 코드

 

//백준5545 최고의피자
 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
bool compare(int i, int j) {
    return i > j;
}
 
int main() {
    int N, A, B, C; //토핑개수, 도우가격, 토핑가격, 도우열량
    cin >> N >> A >> B >> C;
 
    vector<int> d; //토핑 열량 벡터
    for (int i = 0; i < N; i++) {
        int t;
        cin >> t;
        d.push_back(t);
    }
    sort(d.begin(), d.end(), compare); //내림차순 정렬
 
    int doughCal = C / A; //1원 당 도우 열량
    
    int bestCal = doughCal; //최고의 피자의 1원 당 열량 (토핑선택안함)
 
    int totalPrice = A; //총 가격
    int totalCal = C; //총 열량
    for (int i = 0; i < N; i++) {
        totalPrice += B;
        totalCal += d[i];
        if (bestCal < totalCal / totalPrice) {
            bestCal = totalCal / totalPrice;
        }
    }
 
    cout << bestCal;
 
}