Codeforces #1418A Buying Torches

문제

https://codeforces.com/problemset/problem/1418/A

걸린 시간

02 : 00 : 00 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 987654321
typedef long long ll;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        ll x, y, k;
        cin >> x >> y >> k;
        ll coal = k*y;
        ll sticks = k+coal-1;
        ll total = sticks/(x-1);
        ll other = sticks%(x-1);
        if(other)
            total++;
        cout << total + k << "\n";
    }
    return 0;
}

횃불을 만들기 위한 재료인 막대기와 석탄은 무역가와 거래를 통해 구할 수 있다. k 개의 횃불을 만드려고 할 때 거래의 횟수를 최소화 하여라.

처음엔 그리디로 해결하려 했지만 모든 입력이 최대 10억이기 때문에 O(n) 으로도 문제를 해결할 수 없었다. 최소 거래 횟수를 구하는 수식을 작성해서 풀이해야 하는 수학 문제였다.