[백준 1500번] 최대 곱 (C++)

문제 링크 : https://www.acmicpc.net/problem/1500

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

const int MOD = 1000000007;

int main() {
    
    int S, K;
    cin >> S >> K;
    
    int tmp1 = S/K;
    int tmp2 = S%K;
    long long result = 1;

    for(int i=0; i<K; i++)
    {
        if(tmp2 > 0) 
        {
            result*=(tmp1+1);
            tmp2--;
        }
        else result *= tmp1;
    }

    cout << result;

    return 0;
}

 

K개를 맞춰야 하므로, 우선 S/K를 통해 평균 값을 구해준다.

이후 S%K를 통해 나머지 누락된 값을 구해준다.

 

최대 값이 되려면, 모든 수의 값 차이가 최소한으로 적어야 한다.

ex) 5 * 3 * 3 < 4 * 4 * 3

따라서 K번 동안 존재하는 나머지 값 동안 tmp1에 1을 더해서 result에 곱해주고, 나머지 값을 감소시켜준다.

이외에는 평범하게 tmp1 값을 곱해서 최대 값을 구해준다.