[백준][C++] 10539: 수빈이와 수열

문제 링크: https://www.acmicpc.net/problem/10539

 

 

수식을 세워서 풀면 됩니다. N의 조건이 100개 이하라서 O(N^2) 알고리즘도 되긴 하는데 그렇게 풀면 재미없잖아요. 수식으로 풀어봅시다

 

\[ B_i = \left ( \sum_{k=1}^{i}A_k \right ) \biggm / i \tag{1} \]

문제에서 주어진대로 수열 A와 B의 관계를 식으로 나타내면 (1)과 같은데요

 

\[ A_i = i \times B_i - \sum_{k=1}^{i-1} \tag{2} \]

(1)을 \(A_i\)를 기준으로 변경해보면 (2)처럼 정리할 수 있습니다.

이 수식을 이용하면 입력되는 \(B_i\)들로 \(A_i\)를 만들 수 있습니다.

 

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n;
	cin >> n;
	long long sum = 0;
	for (int i = 1; i <= n; ++i) {
		long long in;
		cin >> in;
		if (i == 1) {
			cout << in << ' ';
			sum += in;
		}
		else {
			cout << i * in - sum << ' ';
			sum += i * in - sum;
		}
	}
	

	return 0;
}

수열값의 범위가 10억 이하니까 long long을 썼습니다.