[BOJ] 1500 :최대 곱 -travelbeeee

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

---

[ 알고리즘풀이 ]

 합이 S가 되게 K개의 수를 나눌 때 우리는 곱이 최대가 되게 해야한다. 즉, 숫자들이 몇몇은 엄청 작고 몇몇은 엄청 큰게 아니라 다들 (S / K) 에 비슷하게 배분이 되어야만 곱이 최대가 된다. 따라서, K개의 숫자가 모두 (S / K)로 시작해서 (S % K)개 만큼만 1씩 더해주면 가장 비슷하게 숫자들을 배분할 수 있다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int S, K;
	cin >> S >> K;
	long long ans = 1;
	for (int i = 0; i < K; i++) {
		if (i < S % K)
			ans = 1L * ans * (S / K + 1);
		else
			ans = 1L * ans * (S / K);
	}
	cout << ans;
}

---