Codeforces #1409B Minimum Product

문제

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

걸린 시간

00 : 55 : 43

풀이

C++

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

ll a, b, x, y, n;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tc;
    cin >> tc;
    while(tc--){
        cin >> a >> b >> x >> y >> n;
        ll A, B, N, decN, ans = INF;
        ll decA = a-x, decB = b-y;
        // A -> B
        A = a, B = b, N = n;
        decN = min(N, decA);
        N -= decN;
        A -= decN;
        decN = min(N, decB);
        B -= decN;
        ans = min(ans, A*B);
        // B -> A
        A = a, B = b, N = n;
        decN = min(N, decB);
        N -= decN;
        B -= decN;
        decN = min(N, decA);
        A -= decN;
        ans = min(ans, A*B);
        cout << ans << "\n";
    }
    return 0;
}

문제는 두 수 a, b를 문제의 조건을 만족하는 범위에서 n만큼 적절히 나누어 각각 감소시켰을 때, 두 수의 곱이 최소가 되도록 하려고 한다.

처음엔 값이 최소가 되는 경우를 여러 가지 생각해보고 주어진 값에 따라 처리를 다르게 하려 했지만 경우의 수가 너무 많았다. 다시 잘 생각해보니 두 수 a, b에서 가능한 대로 n만큼 모두 감소시키기 때문에 나올 수 있는 경우의 수는 1) a를 최대한 감소시키고 남은 값으로 b를 감소, 2) b를 최대한 감소시키고 남은 값으로 a를 감소 두 가지뿐이였다.

값의 범위를 잘 고려하면서 두 가지 경우의 값을 구해 비교한 후 최소값을 출력하면 된다.