[백준] 1500번: 최대 곱

Solved.ac 실버2
https://www.acmicpc.net/problem/1500

설명

세준이는 정수 S와 K가 주어졌을 때, 합이 S인 K개의 양의 정수를 찾으려고 한다. 만약 여러개일 경우 그 곱을 가능한 최대로 하려고 한다. 가능한 최대의 곱을 출력한다.
만약 S=10, K=3이면, 3,3,4는 곱이 36으로 최대이다.

입력

첫째 줄에 두 수 S와 K가 주어진다. K는 20보다 작거나 같고, S는 100보다 작거나 같으며 K보다 크거나 같다.

출력

첫째 줄에 정답을 출력한다. 답은 9223372036854775807보다 작다.

해결 Tip

알고리즘 분류

• 수학

이 문제는 끈으로 직사각형 만들기랑 비슷하다.
끈의 길이가 정해져 있을 때, 넓이가 가장 큰 직사각형을 만드려면 직사각형을 만들어야 한다.

이와 비슷한 방식으로 문제를 접근하면 최댓값을 갖기 위해선 K개의 수가 최대한 같은 수이면 된다.
대신 정수로만 쪼개야 하기 때문에, 소숫점이 발생한다면 올림/내림으로 정수로 바꾼다.

마지막으로, 출력해야 하는 값이 상당히 클 수도 있으니 자료형을 long long으로 설정해주면 문제가 풀린다.

코드

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int main() {
    // decleration
    fastio;
    int N, K;

    // input
    cin >> N >> K;

    // solve
    float q = (float) N / K;
    int upper = ceil(q), lower = floor(q);
    
    int upper_cnt = 0, lower_cnt = 0;
    while (N/upper != K-lower_cnt) {
        lower_cnt++;
        N -= lower;
    }
    upper_cnt = K - lower_cnt;

    unsigned long long int ans = pow(upper, upper_cnt) * pow(lower, lower_cnt);

    // output
    cout << ans;

    return 0;
}