[코드트리/C++] 저것도 먹을거란 말이야 (Greedy / Math)

문제

https://www.codetree.ai/problems/i-want-to-eat-more/description

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

구상

간단히 문제를 보면 내용이 은근 많아서 꽤나 복잡한 문제라고 생각하기 쉽지만,, 본질을 꿰뚫어보면 사실 정말 간단한 문제이다. 나도 헤맨 부분인데, 사실 한 음식에 대해 개수가 다양하게 주어지는데, n일 동안 최대 3번을 먹을 수 있기에 최대 3개로 저장하면 된다. 그렇게 되면, 어제 먹은 맛과는 다른 맛만 먹으면서 n일을 버티면 다이어트 성공!이 된다. 그리고.. 정말 놀라운 점은 해당 문제에서는 맛만 중요하지, 음식의 종류는 아무짝에도 쓸모가 없어진다. 정말....이거 파악하고 현타가 너무 심하게 왔다.. 이렇게 쉬운데.. 왜 kaupc때는 이걸 파악 못했찌-- 현타가 오면서 동시에 대회때 긴장만 안하고 본질만 꿰뚫으면 훨씬 더 잘 풀 수 있겠다는 자신감도 생겼다 ㅎㅎ 

 

해당 문제는 두가지 방법으로 풀 수 있다. 

 

첫째, greedy를 이용한 풀이인데, n일 동안 반복하며 음식의 수가 가장 많은 맛을 먹는데, 어제와 다른 맛의 음식만 먹으면 된다. 그렇게 n일을 버티면 다이어트 성공이다. 

 

둘째, math로도 풀 수 있는데, 3개의 맛을 번갈아서 먹어야 한다는 특징을 통해 식을 하나 도출할 수 있다. 맛에 따른 음식의 개수에 따라 내림차순 정렬을 하여 a, b, c 가 도출되었다고 가정을 해보자. a가 아무리 많아도, b와 c와 함께 n일 동안 번갈아 먹으려면 "a + b + c == n 이라는 조건하"에 a <= b + c + 1 이라는 식이 성립해야 한다. 간단히 예를 들어 a가 4, b가 2, c가 1개라 했을 때, ababaca로 성립한다. 그런데, a가 1개가 늘어 5가 되면, ababacaa 가 되어 a가 최소 한번은 연이어 존재하게 된다. 그러니, 우선 a + b + c가 n 초과라면, a + b + c == n이 될때까지 가잔 많은 맛을 소진한다. 이후, a <= b + c + 1가 성립하는지 확인하면 된다. 기존 a + b + c가 n 미만이라면 애초에 불가능한 다이어트이니, "FAIL"을 반환하면 된다. 

 

1. Greedy 이용한 풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;

// 저것도 먹을 거란 말이야

int days;
int types;
vector<pair<int, int>> food = { {0, 0}, {0, 1}, {0, 2} }; // 개수 맛
string res = "SUCCESS";
int before = -1; // 직전에 먹은 맛


void solution() {

    sort(food.begin(), food.end(), greater<pair<int, int>>()); // 개수로 내림차순 정렬

    if (days > food[0].first + food[1].first + food[2].first) res = "FAIL"; // 있는 음식보다 먹어야 하는 날이 더 크면 fail

    while (days--) { //  n일 동안 반복하며 음식의 수가 가장 많은 맛을 먹는다. 이때, 직전에 먹은 음식의 맛과 달라야 한다. 
        sort(food.begin(), food.end(), greater<pair<int, int>>()); // 개수로 내림차순 정렬

        if (food[0].second == before) { // 이미 먹었던 거 -> 두번째 맛 선택
            if (food[1].first > 0) {
                food[1].first--; before = food[1].second;
            }
            else {
                res = "FAIL"; break;
            }
        }
        else { // 가장 많은 첫번째 맛 선택
            if (food[0].first > 0) {
                food[0].first--; before = food[0].second;
            }
            else {
                res = "FAIL"; break;
            }
        }
    }

    cout << res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> days >> types;
    for (int i = 0; i < types; i++) {
        string a; int b, c; // 맛, 개수
        cin >> a >> b >> c;
        int num = c >= 3 ? 3 : c;
        food[b].first += num;
    }

    // 로직
    solution();


    return 0;

}

 

2. Math 이용한 풀이 + 코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<map>
#include<queue>
#define MAX 101
#define INF 987654321
#define endl "\n"
using namespace std;
// 저것도 먹을 거란 말이야
int days;
int types;
vector<pair<int, int>> food = { {0, 0}, {0, 1}, {0, 2} }; // 개수 맛
string res = "SUCCESS";

int before = -1; // 직전에 먹은 맛


void solution() {

    sort(food.begin(), food.end(), greater<pair<int, int>>()); // 개수로 내림차순 정렬

    if (days > food[0].first + food[1].first + food[2].first) res = "FAIL"; // 있는 음식보다 먹어야 하는 날이 더 크면 fail

    else if (days < food[0].first + food[1].first + food[2].first) { // 음식보다 먹어야 하는 날이 더 작으면 음식을 days에 맞게 줄이기
        // 가장 많은 맛부터 없애면 됨. 이때는 같은 맛이 반복되어도 됨.
        while (days < food[0].first + food[1].first + food[2].first) {
            sort(food.begin(), food.end(), greater<pair<int, int>>()); // 개수로 내림차순 정렬
            food[0].first--;
        }
    }

    sort(food.begin(), food.end(), greater<pair<int, int>>()); // 개수로 내림차순 정렬

    if (food[0].first > food[1].first + food[2].first + 1) res = "FAIL";

    cout << res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    // 입력
    cin >> days >> types;
    for (int i = 0; i < types; i++) {
        string a; int b, c; // 맛, 개수
        cin >> a >> b >> c;
        int num = c >= 3 ? 3 : c;
        food[b].first += num;
    }

    // 로직
    solution();


    return 0;

}