c언어 3020번 개똥벌레 (백준)

#include <stdio.h>

int main(void)
{
	int n, h, tmp;
	
	scanf("%d %d",&n, &h);
	
	int odd[500001]={}, even[500001]={}; //석순 : odd, 종유석 : even
	
	for(int i=1; i<=n; i++) //석순 또는 종유석의 크기 입력
	{
		scanf("%d", &tmp);
		if(i&1) odd[tmp]++; //홀수번
		else even[tmp]++; //짝수번
	}
	
	for(int i=h-2; i>0; i--) { //누적합 (더 큰것의 개수를 덜 큰것의 개수에 더해줌)
		odd[i] += odd[i+1]; //석순
		even[i] += even[i+1]; //종유석
	}
	
	int min = 1e9, cnt = 0; //최솟값과 이때의 개수
	for(int i=1; i<=h; i++) {
		tmp = odd[i] + even[h-i+1];
		if(min > tmp) { // 더 작다면?
			min = tmp;
			cnt = 1;
		} else if(min == tmp) cnt++; //같다면?
	}
	printf("%d %d", min, cnt); //출력
}

풀이 : 누적합

 

1. 석순과 종유석을 담을 배열들을 만듭니다.

2. 홀수번엔 석순의 값을, 짝수번엔 종유석의 값을 길이에 맡게 증가시켜줍니다.

3. 각각의 석순과 종유석의 누적합을 구합니다.

EX) 석순의 높이가 2인 것이 두개있다는 의미는 석순의 높이가 1인 것이 2개 이상이라는 의미가 됩니다. 즉 긴 것에서 작은것에 값을 누적 시켜줍니다.

4. 최솟값과 이때의 개수를 for문을 이용하여 구해줍니다.

 

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

3020번: 개똥벌레