[BOJ] 1500_최대 곱

최대 곱

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

1500번: 최대 곱

 

최대한 골고루 분배를 하여 곱해주는 것이 가장 효율적이다.
s = 10, k = 3일 때, 10을 3으로 나누었을 때, 3, 3, 3, 1이 된다.
우리는 3묶음으로 하면 되니, 나머지 1을 누군가에게 분배를 해주면 된다.
따라서, 3 3 4로 36이 된다.
만일 11을 3으로 나누게 된다면, 3, 3, 3, 2가 되며, 이 2또한 누군가에게 분배를 해준다.
3 4 4로 48이 된다.

이를 정리하면, 전체 k개에서 나머지만큼 분배할 mod수를 제외하고는 전부 s/k의 값을 곱해준다.
그 후 mod를 분배하여 추가한 (s/k+1)을 mod수 만큼 곱해준다.

 

• 정답 코드

    #include<iostream>
    #include<cmath>
    using namespace std;
    unsigned long long int cal = 1;
    int s, k;
  
    int main() {
        cin >> s >> k;
        int mod = s % k;
        int div = s / k;
  
        cout << fixed;
        cout.precision(0);
        if (!mod)
            cout << pow(div, k);
  
        else {
  
            for (int i = 0; i < k-mod; i++) {
                cal = (unsigned long long int)cal * div;
            }
            for (int i = 0; i < mod; i++) {
                cal = (unsigned long long int)cal * (div+1);
            }
            cout << cal;
        }
        return 0;
    }