c언어 33705번 마스코트 정하기

#include <stdio.h>
int main(void) {
	int n,m,i,a[200001]={},b;
	scanf("%d",&n);
	for(i=1;i<=n;i++) {
		scanf("%d",&m);
		a[i]+=a[i-1];
		if(m==1)++a[i];
	}
	if(a[n]*2>=n) b=0;
	else {
		for(i=1;i<=n;i++) if(a[i]*2>=i || (a[n]-a[n-i])*2>=i) {b=1;break;}
		if(i==n+1) b=2;
	} printf("%d",b);
}

풀이 : 누적합

 

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

 

 

여기서 중요한 것은 내쫓는 것을 최대 2번까지만 하면 반드시 1번이 마스코트로 뽑힐 수가 있습니다.

 

0번 : 입력받은 데이터들 중 1이 ⌈m/2⌉ 이상이면 됩니다.

1번 : 1번만 내쫓는 경우는 2가지로 볼 수 있습니다.

         양쪽 끝단 중 하나에서 부터 시작하여 범위를 지정

         양쪽 끝단 이 아닌 중간범위를 지정

2번 : 양쪽 끝단을(두 번) 시작으로 범위를 지정

여기서 중요한 것은 1번에서 중간범위를 지정하는 것을 계산할 필요가 없습니다. 

ex)

001100 이런 경우 양끝단을 기준으로 한번 날려주면 됩니다. 0011 (1번)

0010100 이런 경우 중간범위를 한 번 날려도 다시 또 한번 범위를 지정후 날려야 합니다. (2번)

0100000 이런 경우 한쪽만 날려주면 됩니다 01 (1번)

00100001 이런 경우도 그냥 한쪽만 날려주면 됩니다. 1(1번)

 

즉 범위를 지정하여 1번 내쫓는다고 할때, 굳이 중간범위를 지정하여 내쫓을 필요가 없습니다. 중간범위를 지정하여 마스코트를 달성할 수 있는 모든 경우는, 양쪽 끝단중 하나를 시작으로 하여 범위를 지정해서 날리는 것으로 대체가 가능하기 때문입니다. 가장 큰 이유는 중간 범위를 지정하여 계산하기에는 시간이 너무나도 많이 걸립니다.

 

고로

n개의 데이터를 받은 다음 1이 ⌈m/2⌉ 이상 개라면 0을 출력

(아니라면)->양쪽에서부터 시작하여 1이 ⌈m/2⌉ 이상 을 넘는 경우가 발생하면 1을 출력

(위도 아니라면)-> 2를 출력하면 됩니다.

 

빠른 계산을 위해, 누적합을 이용하여, 특정 범위의 1의 개수를 저장해 놓은 후 이를 이용하면 됩니다.