[백준 - 22896번] Closest Pick - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그리디, 수학, 정렬, 확률론

입력

출력

제한

• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 30.
• 1 ≤ Pi ≤ K, for all i.
• 1 ≤ K ≤ 10^9

풀이

당첨 확률을 최대로 할 수 있는 두 티켓을 선택해야 한다.

문제에 보면 조건이 두 개인 것 같지만 결국 내가 선택한 티켓 중 하나라도 c와 가장 가까운 티켓이 있다면 승리하는 것이다.

그러면 어떤 티켓을 골라야 당첨 확률을 최대로 할 수 있을까?

이를 바텀-업으로 풀이해 보겠다.

K가 10일 때 이미 고른 티켓이 8이라면 어떤 수를 골라야 할까? 7과 9를 골라야 한다.
7이 선택되면 7, 6, 5, 4, 3, 2, 1가 c일 때 승리하기 때문에 당첨 확률은 7/10이고,
9가 선택되면 9, 10으로 당첨 확률은 2/10로 총 9/10이 된다.

이를 통해 알 수 있는건 이미 고른 티켓보다 바로 앞에 티켓을 선택할 때 그 앞에 어떠한 티켓도 없다면 1~선택한 수 범위는 승리할 수 있는 범위가 된다. (앞 -> 뒤로 바꾸면 똑같음)

그래서 1 ~ 첫 번째 티켓 - 1, 마지막 티켓 + 1 ~ K의 범위를 list에 넣어준다.

그러면 이미 고른 티켓 사이에서는 어떠한 수가 당첨 확률을 최대로 할 수 있을까?

이 경우도 가장 왼쪽이든 가장 오른쪽이든 선택하면 된다. (당연히 이미 고른 티켓을 제외하고)

그런데 지금까지 말한 것은 각 구간에서 하나의 수를 선택한 경우다.

그래서 두 수를 선택하는 경우도 따져봐야 한다.

이미 고른 티켓 사이에 두 수를 선택한다면 승리하는 구간은 그 구간 자체가 된다.

예를 들어 3 6이 이미 선택되었을 때 4, 5를 선택한다면 3 6사이 구간 4 5 6자체가 승리하는 범위가 된다.

그래서 정리하면 각 구간에서 하나의 수를 선택하는 경우와 앞 뒤 구간은 제외하고 각 구간에서 두 수를 선택하는 경우로 나눠서 당첨 확률이 큰 값을 골라 출력하면 된다. (앞 뒤 구간 같은 경우는 이미 고른 티켓 사이가 아니기 때문에 하나의 수를 고르는 것만으로도 전체 구간이 승리하는 범위가 됨)

각 구간에서 하나의 수를 선택하는 경우 당첨 확률을 최대로 하는 두 구간을 선택하면 되고,

각 구간에서 두 수를 선택하는 경우는 당첨 확률을 최대로 하는 한 구간을 선택하면 된다.

이를 비교해 출력하면 AC된다.

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

소스 코드

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

public class Main {
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int T = Integer.parseInt(br.readLine());
      StringBuilder sb = new StringBuilder();
      
      for(int r=1; r<=T; r++) {
          sb.append("Case #" + r + ": ");
          
          StringTokenizer st = new StringTokenizer(br.readLine());
          int N = Integer.parseInt(st.nextToken());
          int K = Integer.parseInt(st.nextToken());
          int arr[] = new int[N];
          
          StringTokenizer st2 = new StringTokenizer(br.readLine());
          for(int i=0; i<N; i++) {
              arr[i] = Integer.parseInt(st2.nextToken());
          }
          
          Arrays.sort(arr);
          
          ArrayList<Integer> list1 = new ArrayList<>(); //구간에서 하나만 선택하는 경우
          ArrayList<Integer> list2 = new ArrayList<>(); //구간에서 두 수를 선택하는 경우
          
          if(arr[0] - 1 > 0) {
              list1.add(arr[0] - 1);
          }
          
          if((K + 1) - arr[N - 1] - 1 > 0) {
              list1.add((K + 1) - arr[N - 1] - 1);
          }
          
          for(int i=1; i<N; i++) {
              int std = arr[i] - arr[i - 1] - 1; //전체 구간
              if(std <= 0) {
                  continue;
              }
              list2.add(std); //구간에 양쪽을 선택하면 양쪽 포함 안쪽 수를 포함할 수 있음
              
              //하나를 선택하는 경우 
              int s = arr[i - 1] + 1;
              int e = arr[i];
              
              if((s + e) % 2 == 0) {
                  list1.add((s + e) / 2 - s);
              } else {
                  list1.add((s + e) / 2 - s + 1);
              }
          }
          
          Collections.sort(list1, Collections.reverseOrder());
          Collections.sort(list2, Collections.reverseOrder());
          
          int mol1 = 0;
          for(int i=0; i<2; i++) {
              if(i >= list1.size()) {
                  break;
              }
              mol1 += list1.get(i);
          }
          
          int mol2 = list2.size() == 0 ? 0 : list2.get(0);
          
          int mol = mol1 >= mol2 ? mol1 : mol2;
          
          sb.append((double) mol / (double) K).append("\n");
      }
      System.out.println(sb.toString().trim());
  }
}