G20159. 동작 그만. 밑장 빼기냐?

문제

제출 코드

• 사용 알고리즘 : 누적합

시작 순서가 정해져 있으므로, 밑장을 빼는 순간 홀수 카드 → 짝수카드로 얻게되는 카드가 달라진다. 이를 이용해서 어느 순간 밑장을 뺐을때 최대가 되는지 모든 경우에 대해 계산하면 되는 문제였다.

정훈이가 밑장을 뺀 뒤로는 짝수번째 카드만을 얻게 되므로, 처음부터 짝수번째 카드들의 누적합을 계산 후 뒤로 갈수록 앞장의 짝수카드를 빼고 홀수카드를 더하는 식으로 계산했다.

맞왜틀..에서 벗어나지 못한 포인트는, 정훈이의 카드 뿐 아니라 상대방의 카드도 밑장빼기가 가능하다는 점이었다. 상대 카드에서 밑장빼기를 할 경우, 밑장을 상대방이 가져가는것 외엔 짝수번째 카드들을 정훈이가 가져가게 되는 것이 변함없다.

package gold;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G20159_stopit {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] card = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		int remains=0;
		for(int i=0; i<N; i++) {
			card[i] = Integer.parseInt(st.nextToken());
			if(i%2!=0) remains += card[i];
		}

		int max=remains;
		for(int j=0; j<2; j++) {
			int sum = 0;
			int tmp = remains - (j==1 ? card[N-1] : 0);
			for(int i=0; i<N; i+=2) {
				sum += card[i];
				if(j==0) tmp -= card[i+1];
				max = Math.max(max, sum+tmp);
				System.out.println(sum+tmp);
				if(j==1) tmp -= card[i+1];
			}

		}

		System.out.println(max);

	}
}