백준 20312번, CPU 벤치마킹 풀이

문제

백준 20312번

풀이

CPU 벤치마킹 사진

 

CPU $ i + 1$번째의 $ j $행은 CPU $ i $번째 $ j $행의 $ m_{i} $배 입니다.

따라서, $ i + 1 $번째 CPU 행의 합 = ($ i $번째 CPU 행의 합 + 1) * $ m_{i} $이 됩니다.

 

이전 행의 값을 계산해두면, 하나를 구할 때 $ O(1) $이므로, 모두 다 구해주는데 $ O(N) $이 걸리겠네요.

소스코드

#include <bits/stdc++.h>

#define all(v) v.begin(), v.end()

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;

const ll MOD = 1e9 + 7;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int n; cin >> n;
	vl vec(n - 1);
	for (auto &i : vec) cin >> i;

	ll ans = 0, prev = 0;
	for (int i = 0; i < n - 1; i++) {
		prev = ((prev + 1) * vec[i]) % MOD;
		ans += prev;
		ans %= MOD;
	}
	cout << ans;
}