[백준/C++] 23559번: 밥(G5)

문제

https://www.acmicpc.net/problem/23559

23559번: 밥

 

 

 

사용한 알고리즘

2022.01.22 - [PS/Algorithm] - [알고리즘 개념정리] 4. 그리디

 

 

풀이

어차피 1000원 짜리는 늘 먹을 수 있으므로
5000원 짜리가 1000원 짜리보다 맛 수치가 높으며(a-b>0) 1000원 짜리와의 차이가 큰 것(gap으로 정렬)을 골라야 한다.

1. 구조체 menu를 만들어 준다. a와 b에는 각각 5000원, 1000원 짜리 학식의 맛의 수치를 담는다.
   gap에는 a-b를 담는다. 
2. gap이 큰 순서대로, gap이 같다면 a가 큰 순서대로 구조체배열을 정렬한다.
3. 이제 첫날부터 마지막 날까지 순회하며 학식의 종류를 정하고 남은 예산(x)과 현재까지의 맛의 합(ans)을 업데이트한다.
4. a-b가 음수라면 b를 선택한다.
5. a-b가 양수라면, 예산을 확인하고 5000원짜리 학식을 고른다.
   현재 a를 골랐을때 남은 예산으로는 남은 날들 동안 1000원짜리 학식조차 못 먹는다면 b를 골라야 한다.

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
// 1. 구조체 menu를 만들어 준다.
//    a와 b에는 각각 5000원, 1000원 짜리 학식의 맛의 수치를 담는다.
//    gap에는 a-b를 담는다.
struct menu{
    int a,b;
    int gap; // = a-b
    bool operator<(menu &other){
        if(gap!=other.gap) return gap>other.gap;
        else return a>other.a;
    }
}m[100001];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    // A-B가 큰 순서대로 정렬
    // A-B가 음수이면 B선택
    // 돈 될때까지 A선택, 그이후로 B선택

    int n,x; cin>>n>>x;
    for(int i=0; i<n; i++){
        cin>>m[i].a>>m[i].b;
        m[i].gap = m[i].a - m[i].b;
    }
    // 2. gap이 큰 순서대로, gap이 같다면 a가 큰 순서대로 구조체배열을 정렬한다.
    sort(m,m+n);

    // 3. 이제 첫날부터 마지막 날까지 순회하며 학식의 종류를 정하고 남은 예산(x)과 현재까지의 맛의 합(ans)을 업데이트한다.
    int ans=0;
    for(int i=0; i<n; i++){
        int dday=n-i-1;
        // 4. a-b가 음수라면 b를 선택한다.
        if(m[i].gap<=0){ 
            ans+=m[i].b;
            x-=1000;
        }
        // 5. a-b가 양수라면, 예산을 확인하고 5000원짜리 학식을 고른다.
        else if(x-5000>=dday*1000){ //현재돈-5000(현재 A를 고름)이 남은날짜*1000보다 커야 A를 고를 수 있음
            ans+=m[i].a;
            x-=5000;
        }
        // 5. 현재 a를 골랐을때 남은 예산으로는 남은 날들 동안 1000원짜리 학식조차 못 먹는다면 b를 골라야 한다.
        else{
            ans+=m[i].b;
            x-=1000;
        }
    }
    cout<<ans;
    return 0;
}