1500 최대 곱

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

1500번: 최대 곱

---

접근

솔직하게, 이 문제는 힌트를 보고 풀었다.

 

힌트를 보고 나니, 이해하지 못했던 내용이었다. 

 

고등학교에서 배운 산술기하평균에 대해서 이해하지 못했었는데 이 문제를 풀면서 조금은 이해하게 되었다.

미흡했던 점

산술 기하 평균이란, 아래 블로그에서 읽는게 더 정확하고 깔끔한 설명이 될 것 같다.

https://m.blog.naver.com/alwaysneoi/100156668769

[산술평균과 기하평균의 관계] 산술평균이 기하평균보다 항상 크거나 같다.

 

글을 읽다보면, 문제에서 말하는 최대 곱이란 기하평균을 의미하는걸 알게 된다. 

 

$\sqrt[k]{a_1 \times a_2 \times ... \times a_k}$가 최대일 때 $a_1, a_2 ... a_k$는 산술 평균의 그것과 같은 값을 갖게 될 것이다.

 

합이 S인 k개의 정수를 골라 모두 곱한 값이 최대일 때 기하 평균이 산술 평균과 같으므로 산술 평균에서 얻은 값을 이용해 최대 곱을 구할 수 있다. 

 

실수값을 다루다가는 오차가 생길 수 있으므로 정수로만 계산하기로 했다. 

 

S가 26이고 K가 7이라고 할 때, 산술 평균은 ${26\over7} = 3.714... = 7 \times 3 + 5$이므로 몫인 3을 원소로 두고 나머지 5를 각 원소에게 배분한다고 하면 최대 곱은 $3\times3\times4\times 4\times4\times4\times4$이다. 

 

K에서 나머지를 뺀 크기만큼 몫을 곱해주고, 나머지의 크기만큼 몫 + 1을 곱해준다.

---

#include <iostream>
int main() {
  int S, K;
  scanf("%d %d", &S, &K);
  long long res = 1;
  for (int i = 0; i < K - S % K; i++) {
    res *= S / K;
  }
  for (int i = 0; i < S % K; i++) {
    res *= S / K + 1;
  }
  printf("%lld", res);
}