[백준 - 30410번] 접시 포개기 - Java

문제 링크

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

문제

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

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 2 \times 10^5)$ 

두 번째 줄에 $N$개의 정수 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 주어진다. $(1 \le A_i \le 2)$ 

출력

남아있는 가장 두꺼운 접시의 두께의 최댓값을 출력한다.

풀이

구현이 좀 까다로운 문제였다.

접시의 두께를 최대화하기 위해서는 연속적인 2의 구간을 최대로 해야 한다.

2의 구간을 최대로 늘리기 위해서는 1로 인해서 끊어진 2의 구간을 연결해야 한다.

만약 1이 짝수인 경우는 앞 뒤에 2의 구간을 연결할 수 있지만, 홀수인 경우에는 앞 뒤에 2의 구간을 연결할 수 없다. ex) 2 2 1 1 1 2

그래서 이러한 경우는 2의 구간에서 1의 구간을 연결했을 때 비교해 최적 해를 구하면 된다.

예를 들어 입력이 다음과 같을 때
2 2 1 1 1 2 1 1 1 1 1

홀수인 1의 구간이 두 곳이며,

첫 번째 2의 구간과 첫 번째 1의 구간을 연결한다면 2의 연속된 개수는 3이된다.

두 번째 2의 구간은 첫 번재 1의 구간과 두 번째 2의 구간을 연결할 수 있기 때문에 2의 연속된 개수는 4가 된다.

그래서 최적 해는 4가 되는 것이다.

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

소스 코드

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

class Info {
    int num, cnt;
    Info(int num, int cnt) {
        this.num = num;
        this.cnt = cnt;
    }
}

public class Main {
    static int N;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      N = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      int[] arr = new int[N];
      for(int i=0; i<N; i++) {
          arr[i] = Integer.parseInt(st.nextToken());
      }
      
      ArrayList<Info> list = new ArrayList<>();
      
      int cnt = 1;
      for(int i=1; i<N; i++) {
          if(arr[i] == arr[i - 1]) {
              cnt += 1;
          } else {
              list.add(new Info(arr[i - 1], cnt));
              cnt = 1;
          }
      }
      
      list.add(new Info(arr[N - 1], cnt));
      
      ArrayList<Info> newList = new ArrayList<>();
      for(int i=0; i<list.size(); i++) {
          if(list.get(i).num == 1 && (i == 0 || i == list.size() - 1 || list.get(i).cnt % 2 == 0)) {
            list.get(i).num = 2;
            list.get(i).cnt = list.get(i).cnt / 2;
          }
          
          if(i == 0) {
              cnt = list.get(i).cnt;
          } else {
              if(list.get(i).num == list.get(i - 1).num) {
                  cnt += list.get(i).cnt;
              } else {
                  newList.add(new Info(list.get(i - 1).num, cnt));
                  cnt = list.get(i).cnt;
              }
          }
          
          if(i == list.size() - 1) {
              newList.add(new Info(list.get(list.size() - 1).num, cnt));
          }
      }
      
      int max = 0;
      for(int i=0; i<newList.size(); i++) {
          if(newList.get(i).num == 1) {
              continue;
          }
          int len = newList.get(i).cnt;
          if(i == 0) {
              if(i + 1 < newList.size()) {
                  len += newList.get(i + 1).cnt / 2;
              }
          } else if(i == newList.size() - 1) {
              if(i - 1 >= 0) {
                  len += newList.get(i - 1).cnt / 2;
              }
          } else {
              if(newList.get(i).num == 2) {
                  len += newList.get(i - 1).cnt / 2 + newList.get(i + 1).cnt / 2;
              }
          }
          if(max < len) {
              max = len;
          }
      }
      if(max == 0) {
          System.out.println(1);
      } else {
          int k = 1;
          while(Math.pow(2, k) <= max) {
              k += 1;
          }
          System.out.println((int) Math.pow(2, k - 1) * 2);
      }
  }
}