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

문제 링크

---

접근 방법

예제로 답을 구해보면서 규칙성을 찾았고 누적합 배열을 만들어서 풀이했다.

 

입력값인 카드의 값들은 num[]에 저장하고

순서대로의 누적합(정훈) sum[]과 뒤에서부터의 누적합(상대방) bsum[]을 구했다.

 

6
3 2 5 2 1 3

문제 예제의 경우

위처럼 누적합 배열을 먼저 생성하고

 

그림처럼 규칙에 의해 sum의 값과 bsum의 값을 더한다.

정훈이가 얻을 수 있는 카드 값의 합은 7, 8(3+5), 11(8+3), 9가 된다는 것을 알 수 있다.

하지만 이는 밑장 빼기한 카드를 정훈이가 갖는 경우만 계산한 결과이다.

 

카드를 밑장 빼기해서 상대방에게 주는 경우도 고려해야한다!

 

6
3 2 5 7 3 1

위 예제의 경우 아까처럼 계산하면 10, 11, 9, 11로 최대값이 11이 나오지만 이는 오답이다.

카드를 밑장 빼기하여 상대방에게 주는 경우는 그림처럼 sum+bsum을 한 후

마지막 장을 빼준 값이 정훈이의 카드 합이 된다.

따라서 12(3+10-1), 15(8+8-1)도 나올 수 있기 때문에 답은 최대값인 15가 된다.

---

삽질했던 부분

밑장빼기를 해서 상대방에게 주는 경우를 생각하지 못했다 ㅎㅎ...

---

후기

여러모로 창의적인 사고를 할 수 있었던 좋은 문제였다

 

---

코드

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

/*
 *  20159. 동작 그만. 밑장 빼기냐?
 *  https://www.acmicpc.net/problem/20159
 */
public class Main {
	static int N, ans, num[], sum[], bsum[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		num = new int[N];
		sum = new int[N];
		bsum = new int[N];
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++)
			num[i] = Integer.parseInt(st.nextToken());
		sum[0] = num[0];
		for (int i = 2; i < N; i += 2)
			sum[i] = sum[i - 2] + num[i];
		bsum[N - 1] = num[N - 1];
		for (int i = N - 3; i > 0; i -= 2)
			bsum[i] = bsum[i + 2] + num[i];

		// 나한테 밑장 빼기
		ans = sum[N - 2];
		for (int i = N - 1; i >= 3; i -= 2)
			ans = Math.max(ans, bsum[i] + sum[i - 3]);
		ans = Math.max(ans, bsum[1]);

		// 상대방한테 밑장 빼기
		for (int i = 0; i < N - 2; i += 2)
			ans = Math.max(ans, sum[i] + bsum[i + 1] - num[N - 1]);
		System.out.println(ans);
	}
}