[백준] 20159 동작 그만 밑장 빼기냐

1. 문제

www.acmicpc.net/problem/20159

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

2. 접근방법

밑 장 빼기를 딱 한번 할껀데 그걸 언제 하는게 최고인지를 찾는 문제

골드 5 치고는 꽤나 머리 아팠다.

 

우선 밑장 빼기를 할때 일어나는 상황을 보자

 

정상

너 : 2 4 6 8

나 : 1 3 5 7

3번에서 밑장빼기

너 : 2 3 5 7

나 : 1 8 4 6

 

정상

너 : 2 4 6 8

나 : 1 3 5 7

4번에서 밑장빼기

너 : 2 8 5 7

나 : 1 3 4 6

 

여기서 보면 3번과 4번 카드가 두번째로 나눠주게 되는 카드였는데

밑장빼기를 하게 되면 세번째 카드부터 순서가 바뀌는 것을 볼 수 있다.

 

그리고 나의 차례에 밑장빼기를 하느냐 너의 차례에 하느냐에 따라

마지막카드를 내가 가지는지 상대가 가지는지를 선택 할 수 있다.

 

자 이제 밑장빼기를 할때 고려해야할 조건은 이 두가지가 다이다.

 

밑장빼기를 할 순번 뒤로 받게 될 나와 너의 숫자 합의 차이와

그 때 마지막 카드를 받느냐 내 카드를 들고 있느냐를 선택했을 때 나오는 차이를

합한 것이 가장 큰 상황일 때 밑장빼기를 하면 된다.

 

즉 위 상황에서

4번과 6번 카드의 합과 5번과 7번 카드의 합의 차이와

3번카드 보다 8번카드의 숫자가 더크다면 8번과 3번의 차이까지 고려해서

다른 모든 순번보다 더 큰 이득을 볼 수 있다면 그 때 밑장빼기를 하면 된다.

 

추가로 마지막 순번의 카드인 7번과 8번은 뒤 카드가 없으므로

7, 8 을 바꾸기만 할 때의 경우도 고려 해주어야 한다.

 

3. 자바 코드

package Gold;

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

public class P20159동작그만밑장빼기냐 {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(br.readLine());
		int map[] = new int[N + 1];
		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= N; i++)
			map[i] = Integer.parseInt(st.nextToken());
		int even[] = new int[N / 2];
		int odd[] = new int[N / 2];
		int preeven = 0, preodd = 0;
		for (int i = N - 1; i > 0; i--) {
			if (i % 2 == 0) {
				even[i / 2] = preeven + map[i];
				preeven = even[i / 2];
			} else {
				odd[i / 2] = preodd + map[i];
				preodd = odd[i / 2];
			}
		}
		int max = 0;
		int maxidx = -1;
		for (int i = 1; i <= N / 2; i++) {
			int swap = map[N] - map[i * 2 - 1] > 0 ? map[N] - map[i * 2 - 1] : 0;
			if (i == N / 2) {
				if (swap > max) {
					maxidx = 0;
				}
			} else if (even[i] - odd[i] + swap > max) {
				max = even[i] - odd[i] + swap;
				maxidx = i;
			}
		}
		int sum = 0;
		if (maxidx == 0) {
			for (int i = 1; i < N - 1; i += 2) {
				sum += map[i];
			}
			sum += map[N];
		} else if (maxidx > 0) {
			for (int i = 1; i < (maxidx - 1) * 2; i += 2) {
				sum += map[i];
			}
			sum += even[maxidx];
			if (map[maxidx * 2 - 1] > map[N])
				sum = sum + map[maxidx * 2 - 1];
			else
				sum += map[N];
		} else {
			for (int i = 1; i <= N; i += 2) {
				sum += map[i];
			}
		}
		System.out.println(sum);
	}

}

4. 마치며

처음엔 다른 방법으로 짜다가 이상하다 싶어서

다시 생각해 풀었다. 그러다 보니 코드가 좀 더러워졌는데 감안하고 봐주세용