https://www.acmicpc.net/problem/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);
}
'프로그래밍 > 알고리즘' 카테고리의 다른 글
6600 원의 둘레 (1) | 2022.09.23 |
---|---|
1059 좋은 구간 (0) | 2022.09.18 |
9465 스티커 (0) | 2022.09.10 |
2502 떡 먹는 호랑이 (0) | 2022.09.07 |
1876 튕기는 볼링공 (0) | 2022.09.06 |
댓글