BOJ 3769 : 최댓값 [C++]

 

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

3769번: 최댓값

 

문제 요약

$m$개의 수 $x_1, x_2, \cdots, x_m$을 정수 $a$, $b$에 대하여 다음과 같이 정의한다. $(a > 0)$

1. $\quad -\frac{1}{\sqrt{a}} \le x_i \le \sqrt{a}$

2. $\quad x_1+x_2+\dotsb+x_m=b\times\sqrt{a}$

자연수 $m$과 정수 $a$, $b$, 짝수인 자연수 $p$가 주어졌을 때,
${x_1}^{p} + {x_2}^{p} + \dotsb + {x_m}^{p}$ 의 최댓값을 구하는 문제이다.

 

접근

루트를 씌운 값이 실수이기 때문에 문제 풀이에 적합하지 않다고 판단하여,
나는 $x_i$를 구하는 대신 $\sqrt{a} \times y_i = x_i$ 라는 식을 세워 $y_i$를 정의하였다.

따라서 1, 2번 식을 $y_i$에 대한 식으로 치환하면

1. $\quad-\dfrac{1}{a} \le y_i \le 1$
2. $\quad y_1+y_2+\dotsb+y_m=b$

와 같이 주어진 식이 알아보기 쉽게 변한다.

이 때, 문제에서 요구하는 값이 최대가 되게 하려면, 역시 각각의 $y_i$가 최대가 되어야 한다.

$a > 0$이므로 $-1 \le -\dfrac{1}{a} \le 0$이다. 따라서 ${(-\dfrac{1}{a})}^p$ 결과값이 원래의 절댓값 $\mid -\dfrac{1}{a}\mid$보다 작아지게 된다.

따라서, $y_i = 1$이 되는 개수를 최대화시키면 된다. 최대화 시킨 $y_i = 1$이되는 개수를 $\alpha$라고 하자.
$\alpha$를 제외한 나머지 $y_i$의 개수를 $other$라고 하면, $\alpha+other=m$이 된다.

이 식과 문제 조건의 2번 식을 통해 $\alpha=\dfrac{m+ab}{a+1}$라는 식을 얻을 수 있다.

이제 $other$를 $other=\beta+1$로 표현할 수 있다. 여기서 $\beta$는 $y_i = -\dfrac{1}{a}$를 만족하는 yi의 개수이다.

그러면 문제에서 요구하는 최댓값이 $\alpha + \beta \times {(-\dfrac{1}{a})}^p + {(\dfrac{m-\alpha-\beta}{a})}^p$로 가장 커지게 된다.

 

#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int T;
	ll m, p, a, b, alpha, beta, els;
	double ans = 0, inv = 0;
	for (cin >> T; T--;) {
		cin >> m >> p >> a >> b;
		p /= 2;
		inv = 1.0 / a;
		alpha = (m + a * b) / (a + 1);
		beta = (alpha - b) * a;
		els = m - alpha - beta;
		ans = alpha * pow(a, p) + beta * pow(inv, p);
		ans += (els - 1) * pow(inv, p);
		ans += pow(inv * (els - 1) * (els - 1), p);
		int real = ans + 0.5;
		cout << real << '\n';
	}
}

 

변수 설명

ans : 출력할 정답을 임시로 계산하기 위한 변수이다.
inv : $\dfrac{1}{a}$를 저장하는 변수이다. (문제에서 $p$가 짝수 꼴이기 때문에 ${(-\dfrac{1}{a})}^p = {(\dfrac{1}{a})}^p$임을 이용)
alpha : $y_i = 1$ 를 만족하는 $y_i$의 개수 $(\alpha)$
beta : $y_i = -\dfrac{1}{a}$ 를 만족하는 $y_i$의 개수 $(\beta)$
els : $m - \alpha - \beta$ ($\alpha$가 최대로 결정된 상태에서 $\beta \times (-\dfrac{1}{a})$의 값은 -1보다 작아질 수 없다. 따라서 $-\dfrac{1}{a}$를 $(other - 1)$개, 남은 하나의 $y_i$를 $\dfrac{m-other+1}{a}$로 설정함으로서 최댓값을 도출할 수 있다.)
real : 출력할 정답이다.