[백준 - 27085번] 최대 점수 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 투포인터

입력

첫 번째 줄에 정수 $N$, $s$가 주어진다.

두 번째 줄에 $N$개의 정수 $A_1, A_2, \ldots, A_N$이 주어진다.

출력

게임오버가 일어나지 않을 때, 리프가 던전을 탈출하는 순간의 점수의 최댓값을 첫 번째 줄에 출력한다.

제한

• $1 \le N \le 2 \times 10^5$ 

• $1 \le s \le N$ 

• $-10^9 \le A_i \le 10^9$ $(1 \le i \le N)$ 

• $A_s = 0$ 

풀이

게임오버가 일어나지 않을 때, 리프가 던전을 탈출하는 순간의 점수의 최댓값을 출력해야 한다.

최댓값을 출력하기 위해서는 항상 max 값을 가지고, 던전에 입장해야 한다.

먼저, 오른쪽 던전부터 공략한다고 해보자, 오른쪽 던전을 공략하다가 어느 순간 막히는 구간이 있을거다. 하지만 그 막히기 전이 항상 max는 아니다. 공략한 던전 중에 max 값이 있을것이고, 그 max를 가지고 왼쪽 던전을 공략한다면, 현재 상태에서 가장 멀리 갈 수 있다.

그래서 max를 가지고 왼쪽 던전들을 공략한다. 왼쪽 던전 또한 공략하다가 어느 순간 막힐 것이다. 만약 max가 오른쪽 던전을 공략했을 때 max보다 커졌다면, 오른쪽 던전을 공략하다가 막혔던 부분을 다시 공략해야 한다. max값이 커졌기 때문에 가능성이 높아졌기 때문이다.

그리고 max가 또 업데이트 되었다면, 왼쪽 던전을 공략한다. 이렇게 반복하다보면, 어느 순간 max가 업데이트 되지 않는 상황이 생기며, 이때 max값을 출력하면 된다.

왼쪽과 오른쪽의 cursor를 두고, 진행하기 때문에 투포인터가 사용됨을 알 수 있다.

그리디 + 투포인터 풀이의 시간 복잡도는 O(N)이다. cursor가 지나온 자리는 다시 탐색하지 않기 때문이다.

소스 코드

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

public class Main {
    static int N;
    static int s;
    static long max = 0;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      s = Integer.parseInt(st.nextToken());
      long[] dungeon = new long[N];
      StringTokenizer st2 = new StringTokenizer(br.readLine());
      for(int i=0; i<N; i++) {
          dungeon[i] = Long.parseLong(st2.nextToken());
      }
      
      long lBeforeMax = 0;
      long rBeforeMax = 0;
      int lCursor = s - 1;
      int rCursor = s - 1;
      while(true) {
          rCursor = moveRight(rCursor, rBeforeMax, dungeon);
          rBeforeMax = max;
          lCursor = moveLeft(lCursor, lBeforeMax, dungeon);
          lBeforeMax = max;
          
          if(max == rBeforeMax) {
              break;
          }
      }
      System.out.println(max);
  }
  
  static int moveRight(int cursor, long beforeMax, long[] dungeon) {
      if(cursor == N) {
          return cursor;
      }
      long v = max - beforeMax + dungeon[cursor];
      cursor += 1;
      while(cursor <= N-1) {
          if(v + dungeon[cursor] < 0) {
              return cursor - 1;
          }
          dungeon[cursor] += v;
          v = dungeon[cursor];
          max = Math.max(max, v);
          cursor += 1;
      }
      return cursor;
  }
  
  static int moveLeft(int cursor, long beforeMax, long[] dungeon) {
      if(cursor == -1) {
          return cursor;
      }
      long v = max - beforeMax + dungeon[cursor];
      cursor -= 1;
      while(cursor >= 0) {
          if(v + dungeon[cursor] < 0) {
              return cursor + 1;
          }
          dungeon[cursor] += v;
          v = dungeon[cursor];
          max = Math.max(max, v);
          cursor -= 1;
      }
      return cursor;
  }
}