백준 19566번 수열의 구간 평균 (c++)

믿을 수 없을만큼 짤막한 답안 코드를 보고도 이해하는데 오랜시간이 걸렸으며

이런문제를 100개쯤 가져다 주고 99개를 답보고 푼다 해도 마지막 한문제조차 스스로 풀 자신이 없기에

너무도 화가난 나머지 블로그에 이 문제를 이해한 방식을 적는다

 

 

 

원소의 수는 20만개 -> 시간초과에 유의해야 함

원소는 양수 뿐만이 아니라 음수와 0이 포함됨 -> 일반적으로 풀 문제는 아님

 

결국 정확히 평균이 K가 나오는 구간을 하나하나 세는 문제가 아니라 기발하고 참신한 풀이법을 이용하여 정답만 가져가야 하는 불합리한 문제라는 것을 알 수 있다.

 

#define ll long long int
using namespace std;

ll n, k;
map<ll, ll> mp;
ll sum = 0;
ll tmp;
ll cnt = 0;
signed main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		ll a;
		cin >> a;
		sum += a;
		tmp = sum - i * k;
		cnt += mp[tmp]++;
	}
	cnt += mp[0];

	cout << cnt << endl;

}

 

10억단위의 수가 20만개나 있으니 모두 더했을때 long long int로 감당이 되나 싶었는데 일단 되는 모양이다.

sum으로 누적합을 구하나, 모든 구간의 누적합을 구해야 하기 때문에 진짜 모든 구간을 구했다가는 20만x20만으로  시간초과가 날 것이다.

 

그래서 tmp라는 오차의 개념이 등장했다.

 

sum은 i개의 원소의 합이고 원소가 i개일때의 바람직한 누적합은 i * k 일 것이다.

즉 sum이 바람직한 수가 되려면 (sum - i * k) 만큼이 필요하다는 것. (다시말해 (sum - i * k)가 0이라면 해당 구간의 평균이 K라는 뜻이다.)

 

이 오차의 횟수를 저장하는게 핵심이다

 

이부분이 죽어라고 이해가 안됐는데 어쨋든 내가 이해한 방식을 기록해두자면

 

mp[A]들은 전부 0 ~ i 까지의 누적합의 오차 A 의 갯수를 기록해둔 곳이다.

0~6 까지의 누적합의 오차가 5라면 mp[5] 에 1이 더해질 것이고

추후 0~10까지의 누적합의 오차가 5라면 mp[5]에 또 1이 더해질 것이다.

 

이것이 왜 즉시 정답을 저장하는 변수 cnt 에 더해지는가?

 

0~6과 0~10의 예를 들었다. 두 구간의 오차가 동일한 5 라면

(0~10) - (0~6)의 구간 (7~10)의 오차는 5 - 5 = 0일 것이며 오차가 0 즉, 평균 K라는 결과가 나온다

 

고로 같은 수의 오차가 2번이상 나오면 해당 구간 사이에 어떻게든 평균 K를 만들 수 있다는 뜻이므로 cnt에 수를 올려주는 것이다.