[백준 14931] 물수제비 (SUJEBI) (C++)

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

 

문제

---

급격한 기후변화로 최근 대곽나라의 많은 강에서 생태계 교란종이 나타나고 있다. 이에 대곽나라의 이기범 대통령은 국무회의를 주재해 정부 차원의 대책을 논의하게 되었다. 대통령, 국무총리, 환경부 장관은 물론 26부의 장관 및 차관이 모여 열띤 토론을 벌였다. 많은 좋은 의견이 나왔지만 그 중 단 한 계획만이 만장일치로 통과되었으니 일명 Flat Dumpling Plan (수제비 계획)으로, 강에서 돌로 물수제비를 해 여러 생태계 교란종을 맞춰 죽이는 계획이었다. 계획을 이행할 강의 강폭은 L(1 ≤ L ≤1,000,000)로 강을 L개의 연속한 칸으로 모델링할 수 있다. 환경부에서는 강의 1번 칸, 2번 칸, … L번 칸 각각에 살고 있는 생태계 교란종의 치명도에 따라 점수를 매겨 놨다. (고유종이 서식하는 곳도 있으므로 점수가 음수일 수도 있다.) 돌을 두 개 이상 던지기에는 팔이 아팠기에 오직 돌 하나로만 진행하기로 했다. 던져진 돌은 던진 파워에 따라서 일정 간격 d(1≤d≤L)로 뛴다. 즉, d번 칸, 2d번 칸, … [L/d]d번 칸을 지난다. 돌이 거친 칸들의 점수의 합을 최대로 하는 자연수 d를 찾아 정부에 보고하자.

 

입력

---

첫째 줄에 강폭 L이 주어진다.

둘째 줄에는 L개 칸의 점수가 주어진다. 모든 점수는 -50,000 이상 50,000 이하의 정수이다.

 

출력

---

점수를 최대로 하는 d 값과 그 때의 점수를 공백을 사이에 두고 출력한다. 만약 점수를 최대로 하는 d가 여럿 존재할 경우 가장 작은 d를 출력한다. 최대의 점수가 0 이하인 경우에는 계획을 시행하지 않는 것이 나으므로 0 0을 출력한다.

 

문제 풀이

---

브루트포스 문제.

1부터 L까지 d를 설정하여 특정 d일 때 얻어지는 점수를 구하면 된다.

 

아래는 코드.

#include <iostream>
using namespace std;

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

	int L;
	cin >> L;
	int* arr = new int[L + 1];
	int d = 0;
	long long maxSum = 0;
	arr[0] = 0;
	for (int i = 1; i < L + 1; i++)
	{
		cin >> arr[i];
	}
	for (int depth = 1; depth < L+1; depth++)
	{
		long long sum = 0;
		for (int i = depth; i < L + 1; i+=depth)
		{
			sum += arr[i];
		}
		if (sum > maxSum)
		{
			maxSum = sum;
			d = depth;
		}
	}
	cout << d << " "<<maxSum << "\n";
	return 0;
}