c언어 20159번 동작 그만. 밑장 빼기냐? (백준)

#include <stdio.h>

int main(void)
{
	int n, nn, tmp, max = 0;
	scanf("%d", &n);
	
	nn = n/2+1;
	int odd[nn], even[nn], o=1; //홀수번째 누적합, 짝수번째 누적합
	
	odd[0] = even[0] = 0;
	for(int i=1; i<=n; i++) { //요소 입력
		scanf("%d", &tmp);
		if(i&1) odd[o] = tmp+odd[o-1]; //홀수 번째
		else {
			even[o] = tmp+even[o-1]; //짝수 번째
			o++;
		}
	}
	
	nn = n/2;
	
	for(int i=0; i<=nn; i++) { //최댓값 구하기
		tmp = odd[i] + even[nn] - even[i]; //밑장을 빼지 않거나, 뺀 것을 자신에게
		if(max < tmp) max = tmp;
		if(i && i<nn) tmp = odd[i] + even[nn-1]-even[i-1]; //밑장 뺀 것을 남에게
		if(max < tmp) max = tmp;
	} printf("%d", max);
}

풀이 : 누적 합

 

누적합을 이용하되, 홀수번째, 짝수번째로 입력 된 것을 따로따로 누적합으로 만들어 놓습니다.

 

최댓값을 구하는 경우의 수

1. 밑장빼기를 하지 않거나 밑장빼기를 한 것을 자신에게 줌

2. 밑장빼기를 한 것을 상대에게 줌

 

1의 경우 밑장을 빼기 전까지는 홀수 번째의 누적합을 이용하다가, 밑장을 뺀 후부턴, 누적 합을 이용해서 그 구간의 짝수 번째 합을 구해서 이용할 수 있습니다.

 

2의 경우 밑장 뺀 것을 남에게 주므로, 짝수 번째의 누적합을 이용하는 것이

1에서는 even[n/2] - even[i] 이었다면,

2에서는 even[n/2-1] - even[i-1] 이 됩니다.

 

ex) 1 2 3 4 5 6 7 8

3까지 나에게 준 다음 밑장을 뽑아서 나한테 준다면

1 3 6 8 이 되며 이는 odd[2] + even[4] - even[2] 로 구할 수 있습니다.

 

3까지 나에게 준 다음 밑장을 뽑아서 상대에게 준다면

1 3 4 6 이 되며 이는 odd[2] + even[3] - even[1] 로 구할 수 있습니다.

 

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

20159번: 동작 그만. 밑장 빼기냐?