[ boj : 14931 ] 물수제비(SUJEBI)

www.acmicpc.net/problem/14931

14931번: 물수제비 (SUJEBI)

문제 : 수들이 주어지고 각 간격 만큼 점프하여 수들을 더했을때 가장 최대값이 되는 수를 구하여라

 

해설 : L의 범위가 최대 백만이니 1부터 L까지 점프해서 일일히 구해준다고 생각해 봤을때의 시간복잡도는

O(L/1 + L/2 + ..... + L/L-1 + L/L) 이 되겠죠.

충분히 2초안에 들어올 수 있는 시간입니다.

 

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll arr[(int)1e6+1];
pair<ll, ll> f(pair<ll, ll> x, pair<ll, ll> y);

int main()
{
	int l;
	cin >> l;
	for (int i = 1; i <= l; i++)cin >> arr[i];

	pair<ll, ll> ans = { 0,0 };
	for (int d = 1; d <= l; d++) {
		ll sum = 0;
		for (int i = d; i <= l; i += d)
			sum += arr[i];
		ans = f(ans, { d,sum });
	}
	cout << ans.first << " " << ans.second;
	return 0;
}
pair<ll, ll> f(pair<ll,ll> x, pair<ll, ll> y)
{
	if (x.second < y.second)return y;
	else if (x.second == y.second && x.first > y.first)return y;
	else return x;
}