[백준 2811] 상범이의 우울

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

 

구현 문제 

 

일단 모든 우울 구간에서 2T 만큼 꽃을 준다.

최대 우울 구간 리스트를 순회하며, 각각 3T 만큼 꽃을 줘보고 최대값인 경우를 도출한다.

 

flower는 너무 길어서 rose로 썼다.

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

class Main {

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

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int N = Integer.parseInt(br.readLine());

    int[] a = new int[N];
    boolean[] rose = new boolean[N];
    StringTokenizer st = new StringTokenizer(br.readLine());
    for (int i = 0; i < N; i++) {
      a[i] = Integer.parseInt(st.nextToken());
    }

    // 가장 긴 우울기간과 인덱스
    int max = 0;
    List<Integer> l = new ArrayList<>();

    // 모든 구간을 2T로 가정했을 때 꽃 수
    int common = 0;

    // 1. 전처리 - 모든 구간을 2T로 가정하고 마스킹
    for (int i = 0; i < N; i++) {

      // 우울한 날이면,
      if (a[i] >= 0) {
        continue;
      }
      int len = 0;
      int day = i;

      // 우울기간 탐색
      while (i < N && a[i] < 0) {
        i++;
        len++;
      }
      i--;

      // 최장 우울기간 기록
      if (len > max) {
        max = len;
        l.clear();
        l.add(day);
      } else if (len == max) {
        l.add(day);
      }

      // 무조건 줘야하는 꽃(2T) 표시
      int start = Math.max(0, day - len * 2);
      for (int j = start; j < day; j++) {

        if (!rose[j]) {
          rose[j] = true;
          common++;
        }
      }

    }

    // 2. 3T 후보 중 최댓값인 경우 판별
    int ans = common;
    for (int i = 0; i < l.size(); i++) {

      int cur = l.get(i);
      int expected = common;
      int start = Math.max(0, cur - max * 3);

      for (int j = start; j < cur; j++) {
        if (!rose[j]) {
          expected++;
        }
      }

      ans = Math.max(ans, expected);
    }

    System.out.println(ans);
  }
}