Codeforces #1476B Inflation

문제

https://codeforces.com/problemset/problem/1476/B

걸린 시간

02 : 00 : 08

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        double k;
        cin >> n >> k;
        vector<double> p(n), f(n, 0);
        for(auto& i : p) cin >> i;
        f[0] = p[0];
        for(int i = 1; i < n; i++){
            f[i] = f[i-1] + p[i];
        }
        ll m = 0;
        for(int i = 1; i < n; i++){
            if(p[i]/(f[i-1]+m) > k/100){
                m = ceil((100*p[i]-k*f[i-1])/k);
            }
        }
        cout << m << "\n";
    }
    return 0;
}

p0 값은 얼마든지 증가시켜도 되기 때문에 i번째 날의 가격 상승률이 k% 보다 큰지 확인하고, 크다면 k% 이하가 되도록 최소한의 값을 증가시켜주면 된다.

문제를 다 파악해놓고, 주어진 예제만 풀어본 채 최소한의 값을 찾는 계산식을 세웠던 것이 실수였다. 직접 예제를 2~3개 정도 더 만들어보고 수식이 올바른지 확인해 봤어야 했다.

float 자료형은 정수를 2²³, 10⁶ 자리까지 표현할 수 있다. 하지만 중간계산에서 발생할 수 있는 수는 최대 10¹¹ 이기 때문에 2⁵², 10¹⁵ 자리까지 표현 가능한 double 자료형을 사용하여야 한다.