[백준 - 30238번] 카드 게임 - Java

문제 링크

티어: 골드 2
알고리즘: 그리디, 애드 혹

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

문제

입력

각 입력은 여러 개의 테스트 케이스로 이루어져 있다. 첫 번째 줄에 테스트 케이스의 개수 $t$가 주어진다($1 \le t \le 10^{4}$). 다음 줄부터 각각의 테스트 케이스가 주어진다.

각각의 테스트 케이스의 첫 번째 줄에 정수 $n$이 주어진다 ($1 \le n \le 2 \cdot 10^{5}$).

두 번째 줄에 $n$개의 정수 $a_1, a_2, \ldots, a_n$이 공백으로 구분되어 주어진다 ($-10^{9} \le a_i \le 10^{9}$).

모든 테스트 케이스에서 $n$의 총합은 $2 \cdot 10^{5}$를 넘지 않는다.

출력

각각의 테스트 케이스마다 정답을 출력한다.

풀이

성호의 최종 점수의 최댓값을 구해야 한다.

문제에서 정의된 성호의 행동을 보면, 홀수 번째의 카드만 점수를 가져올 수 있다.

그러면 첫 번째 카드를 계속 선택한다면, 모든 카드의 점수를 가져올 수 있는데, 당연히 음수인 경우는 선택하지 않아야 한다. 그래서 두 번째 카드가 음수라면 제거하는 행동을 해서 원하는 양수 카드만 선택하여 최적의 값을 얻을 수 있다.

그러면 다음과 같은 의문이 든다. 첫 번째 카드가 양수이면 상관없지만, 음수라면 어떻게 풀어야 할까?

음수인 경우에는 선택하지 않는게 최선인 것 같지만, 만약 두 번째 카드와의 합이 양수라면 가져오는 것이 최선의 선택이 된다. 왜냐하면 첫 번째 카드를 선택하지 않는 이상은 두 번째 카드를 가져올 방법은 없기 때문이다.

그래서 첫 번째 카드를 선택하고, 이후에는 두 번째 카드가 첫 번째 카드가 되며, 양수이기 때문에 이후 모든 양수 카드를 선택하면 된다. (앞에서 첫 번째 카드가 양수인 경우와 같아짐)

그러면 두 번째 카드와의 합이 음수라면 어떻게 해야할까? 당연히 두 카드를 선택하지 않는 것이 최선이며, 이후 세 번째 카드부터 마지막 카드까지 양수 카드만 선택하면 된다.
양수 카드만 선택할 수 있는 이유는 두 번째 카드를 제거함으로써 세 번째 카드를 제거할 수 있는 위치인 두 번째로 옮겨 줄 수 있기 때문이다.

그래서 다시 한 번 case를 정리하자면,

• 첫 번째 카드가 양수인 경우
  모든 양수 카드를 점수의 포함한다.

• 첫 번째 카드가 음수인 경우

  • 첫 번째 카드와 두 번째 카드의 합이 양수인 경우
    첫 번째 카드 + 모든 양수 카드를 점수의 포함한다.
  • 첫 번째 카드와 두 번재 카드이 합이 음수인 경우
    세 번째 카드부터 마지막 카드중에서 모든 양수 카드를 점수의 포함한다.

이 풀이의 시간 복잡도는 O(N)이다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int t;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      t = Integer.parseInt(br.readLine());
      StringBuilder sb = new StringBuilder();
      for(int k=0; k<t; k++) {
          int n = Integer.parseInt(br.readLine());
          long answer = 0;
          if(n == 1) {
              int a = Integer.parseInt(br.readLine());
              if(a >= 0) {
                  answer += a;
              }
          } else {
              int[] card = new int[n];
              StringTokenizer st = new StringTokenizer(br.readLine());
              for(int i=0; i<n; i++) {
                  card[i] = Integer.parseInt(st.nextToken());
              }
              if(card[0] >= 0) {
                  for(int i=0; i<n; i++) {
                      if(card[i] > 0) {
                          answer += card[i];
                      }
                  }
              } else {
                  for(int i=2; i<n; i++) {
                      if(card[i] > 0) {
                          answer += card[i];
                      }
                  }
                  answer += card[0] + card[1] > 0 ? card[0] + card[1] : 0;
              }
          }
          sb.append(answer).append("\n");
      }
      System.out.println(sb.toString().trim());
  }
}