Boj 26070 c++ 곰곰이와 학식

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

 

치킨을 먹고 싶은 학생, 피자를 먹고 싶은 학생, 햄버거를 먹고 싶은 학생이 주어진다.

현재 있는 식권의 수가 주어진다. 각각의 식권은 다음과 같은 규칙에 따라 교환할 수 있다. 

 

치3 -> 피1
피3 -> 햄1
햄3 -> 치1

 

이때 주어진 식권으로 원하는 음식을 먹을 수 있는 최대 학생의 수를 구해야 한다.

 

우선 생각해봐야 할 점은 식권을 교환할 수록 실질적으로 식권을 사용할 수 있는 인원은 줄어들기에 우선 

해당 음식을 먹고자 하는 학생을 모두 확보한 후 교환해야 한다는 것이다.

 

치킨을 먹고 싶은 학생을 A, 실제 식권의 수를 X라고 하면 A > X 인 경우는 식권을 교환하면 안된다.

교환하지 않고 우선 X명이라도 만족시키는 것이 낫기 때문이다.

하지만 A < X인 경우, 즉 식권이 남아도는 경우에는 식권이 부족한 음식으로 교환해주면 된다.

또한 문제 상에서 교환되는 관계는 순환구조를 이루므로 최소 2바퀴를 돌아야지만 최적해를 구할 수 있다.

 

전체 코드

#include <iostream>
typedef long long ll;
using namespace std;

ll A, B, C, X, Y, Z, ans;

int main() {
    cin >> A >> B >> C;
    cin >> X >> Y >> Z; // 식권의 수

    ll rX, rY, rZ, cnt = 2;
    while(cnt--) {
        rX = X - A;
        if(rX > 0) {
            Y += rX / 3;
            X -= (rX / 3) * 3;
        }
        rY = Y - B;
        if(rY > 0) {
            Z += rY / 3;
            Y -= (rY / 3) * 3;
        }
        rZ = Z - C;
        if(rZ > 0) {
            X += rZ / 3;
            Z -= (rZ / 3) * 3;
        }
     }

    ans = min(X, A) + min(Y, B) + min(Z, C);
    cout << ans;
}