Baekjoon 17357 자동차가 차주 김표준의 편을 들면?

Link https://www.acmicpc.net/problem/17357

결과 1988KB / 172 ms

언어 C++ 17

 

풀이

투포인터 개념을 적용하면 쉽게 풀리는 문제

각 케이스 마다 합을 구한 후 표준 편차 공식을 적용시키면 편하다.

표준편차를 구하기 전 합만 할면 되기 때문에 합을 구하는 과정에서 투포인터를 적용한다.

생각보다 빠르게 돈다.

 

소스코드

#include <iostream>

using namespace std;

const int MAX = 1000;

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

	int n; cin >> n;
	int val[MAX] = {};

	for (int i = 0; i < n; i++)
		cin >> val[i];

	for (int i = 0; i < n; i++) {
		double vMin = 0;
		double vMinPos = 1;
		int sum = 0; for (int j = 0; j < i + 1; j++) sum += val[j];
		int left = 0, right = i;

		while (right < n) {
			double avg = sum / double(right - left + 1);
			double vSum = 0;
			for (int j = left; j <= right; j++)
				vSum += (val[j] - avg) * (val[j] - avg);
			double v = vSum / (right - left + 1);
			if (vMin < v) {
				vMin = v;
				vMinPos = left + 1;
			}

			sum += val[++right] - val[left++];
		}

		cout << vMinPos << '\n';
	}

	return 0;
}