C. Milk Measurement

- kir3i

문제에서 Farmer John은 헛간 벽에 가장 우유를 많이 생산하는 젖소의 사진을 걸어놓습니다.

구해야할 것은 헛간 벽에 걸려있는 젖소의 사진이 바뀌는 횟수입니다.

만약 우유생산량이 가장 많은 젖소가 두 마리로 서로 동점이면 사진을 두 장 걸어야합니다.

따라서 이 문제는 ‘특정 날짜에 최대로 우유를 생산 하는 젖소가 몇 번이나 바뀌는가?’,

즉 최댓값의 위치와 개수가 얼마나 변하는지를 구하는 문제라고 할 수 있습니다.

풀이 방법은 다음과 같습니다.

1. 입력받은 로그를 날짜가 빠른 순으로 정렬한다.

2. 1일부터 100일까지 진행하며 로그 상에 일치하는 날짜가 있으면 우유 생산량의 변화를 반영한다.

3. 해당 일자에서 최댓값을 구하고 기존에 저장해두었던 status와 다르면 status를 갱신한다.

   -> 한 번 count.

우유 생산량 최댓값의 위치, 개수는 비트마스킹을 이용하여 나타냈습니다.

<C++>

#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <algorithm>

using namespace std;

int measure[3] = {7, 7, 7};   //0 - Bessie, 1 - Elsie, 2 - Mildred
vector<pair<int, pair<int, int>>> cowlog;  // {day, {cow_num, d_milk}}

int find_max()
{
    int rtn = 0;
    int max_measure = max(measure[0], max(measure[1], measure[2]));

    for(int i=0; i<3; i++)
        if(measure[i] == max_measure)
            rtn |= 1<<i;
    return rtn;
}

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

    int N;
    cin >> N;

    for(int i=0; i<N; i++)
    {
        int day, d_milk, cow_num;
        string cow_name;
        cin >> day >> cow_name >> d_milk;
        if(cow_name == "Bessie")
            cow_num = 0;
        else if(cow_name == "Elsie")
            cow_num = 1;
        else if(cow_name == "Mildred")
            cow_num = 2;
        cowlog.push_back(make_pair(day, make_pair(cow_num, d_milk)));
    }
    sort(cowlog.begin(), cowlog.end());


    //초기에는 모든 젖소의 생산량이 동일하므로 모든 젖소의 사진이 걸려있다.
    int status = 1<<2 | 1<<1 | 1<<0;
    int logidx = 0;
    int cnt = 0;
    for(int day=1; day<=100; day++)
    {
        for( ; logidx<N; logidx++)
        {
            if(cowlog[logidx].first == day)
                measure[cowlog[logidx].second.first] += cowlog[logidx].second.second;
            else
                break;
        }
        int t = find_max();
        //최댓값의 위치나 개수가 달라진 경우
        if(status != t)
        {
            status = t;
            cnt++;
        }
    }
    cout << cnt;
}