취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17550번 문제인 Inquiry I이다.
문제는 아래 링크를 확인하자.

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

$A_k=a_1^2+\cdots +a_k^2$, $B_k=a_{k+1}+\cdots +a_n$라 하자. 이 때 문제에서 구하고자 하는 값은 $1$ 이상 $n$ 미만의 정수 $k$에 대하여 계산한 $A_k{B}_k$의 값들 중 최댓값이 된다. 따라서 $A_k$와 $B_k$의 값을 미리 빠르게 계산해둘 수 있다면 위 값들을 직접 계산해 답을 구할 수 있다.

한편, $A_k$는 $A_{k-1}+a_k^2$임을 이용하면 모든 $A_k$의 값을 $O(n)$으로 구할 수 있고, 이와 비슷하게 방향을 바꿔 계산하는 것으로 모든 $B_k$의 값을 $O(n)$으로 구할 수 있다. 이는 문제를 해결하기에 충분히 빠른 시간복잡도이다.

위의 관찰을 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

int N, total; ll totals, mx;
int A[1000000];

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		total += A[i];
	}

	for (int i = 0; i < N; i++) {
		total -= A[i];
		totals += A[i] * A[i];
		mx = max(mx, totals * total);
	}
	cout << mx;
}