[Silver V] 포켓몬 GO - 13717

[문제 위치]

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

[문제 풀이]

이 문제는 수학(등차 감소량 계산) 를 통해 해결하는 문제이다.
한 종의 사탕이 M개이고 진화에 K개가 필요하며 진화마다 2개를 환급받으므로 매 진화 시 순감소량은 (K−2)이고 시작 조건은 M≥K이므로 가능한 진화 횟수는 M<K면 0, 그렇지 않으면 e=1+⌊(M−K)/(K−2)⌋가 된다. 모든 종에 대해 e를 합산하고 e가 최대인 이름을 동률 시 먼저 나온 것으로 갱신하면 한 번의 스캔으로 해결한다
아래는 이를 구현한 코드이다.

#include <bits/stdc++.h>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);

int main() {
    FASTIO;
    int N;
    if (!(cin >> N)) return 0;

    long long total = 0;
    string bestName;
    long long bestCnt = -1;

    for (int i = 0; i < N; ++i) {
        string name; long long K, M;
        cin >> name >> K >> M;

        long long e = 0;
        if (M >= K) {
            // 문제 성격상 K >= 3이므로 안전하게 공식 사용
            e = 1 + (M - K) / (K - 2);
        }
        total += e;
        if (e > bestCnt) {
            bestCnt = e;
            bestName = name;
        }
    }

    cout << total << '\n' << bestName << '\n';
    return 0;
}