[백준 - 15790번] 최종병기 활 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 이분 탐색

입력

입력의 첫째 줄에 고무줄의 둘레 N(1 ≤ N ≤ 100000 인 정수)과 절단이 가능한 홈의 개수 M(1 ≤ M ≤ min(N,1000) 인 정수) 그리고 최고의 활을 만들때 필요한 고무줄겹의 수 K(1 ≤ K ≤ M 인 정수)가 주어진다.

이후 두 번째 줄부터 M+1번째 줄까지 고무줄에서 절단이 가능한 홈의 위치 X(0 ≤ X ≤ N-1 인 정수)가 주어진다. 주어지는 홈의 위치는 각각 유일하며 오름차순으로 주어진다.

출력

만들 수 있는 가장 긴 활의 길이를 출력하시오. 만약 활을 만들 수 없다면 -1을 출력하시오

풀이

활의 길이가 최대가 되게끔 절단해야 한다.

이 문제는 전형적인 이분 탐색 문제다.
왜냐하면 고무줄의 최소 길이를 설정했을 때 이 길이가 커질수록 가능성은 낮아지며, 작아질수록 가능성으 높아진다. 그러니까 3으로 설정했을 때 불가능한 경우 3이상 모든 값은 불가능하다.

또한 중요한 점은 처음 절단 홈은 어디든 될 수 있다는 것이다. 그래서 모든 홈을 첫 홈으로 설정하고, 가능한지 가능하지 않은지를 판단해야 답을 구할 수 있다.

그래서 시간 복잡도는 O(logN * M^2)이 된다.

첫 홈을 설정할 때 모든 홈을 기준으로 풀어도 TLE가 나진 않지만, O(M)으로 최적 홈을 설정할 수 있지 않을까? 라는 생각을 해봤다.

그런데 어떤 홈을 기준으로 절단하냐에 따라서 다른 홈을 절단했을 때 남은 길이가 달라지기 때문에 정확하진 않지만 그러한 방법이 없다고 결론 내렸다.

소스 코드

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

public class Main {
    static int N, M, K;
  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());
      M = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());
      int[] slot = new int[M];
      for(int i=0; i<M; i++) {
          slot[i] = Integer.parseInt(br.readLine());
      }
      
      int answer = binarySearch(slot);
      System.out.println(answer);
  }
  
  static int binarySearch(int[] slot) {
      int min = 1;
      int max = 100000;
      while(min <= max) {
          int mid = (min + max) / 2;
          
          if(check(slot, mid)) {
              min = mid + 1;
          } else {
              max = mid - 1;
          }
      }
      return max;
  }
  
  static boolean check(int[] slot, int len) {
      for(int i=0; i<M; i++) {
          //i는 start slot
          int sv = slot[i];
          int cnt = 1;
          int cursor = i + 1 == M ? 0 : i + 1;
          int left = N;
          while(true) {
              if(cnt == K) {
                  if(left >= len) {
                      return true;
                  }
                  break;
              }
              if(cursor == i) {
                  break;
              }
              int v = findLength(sv, slot[cursor]);
              if(v >= len) {
                  sv = slot[cursor];
                  cnt += 1;
                  left -= v;
              }
              cursor = cursor + 1 == M ? 0: cursor + 1;
          }
      }
      return false;
  }
  
  static int findLength(int sv, int v) {
      if(sv < v) {
          return v - sv;
      }
      return N + v - sv;
  }
}