[백준] 풍선 터트리기 - Java 32377

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

 

 

 

우선, 입력값인 x, y, z의 값이 굉장히 크기 때문에 `이분 탐색`으로 접근해야 된다는 생각이 들었다.

(그리고 시간 제한이 0.5초이다)

 

그래서 내가 생각한 키 포인트는 x, y, z에 따른 N번째 풍선을 터트리는 순간을 이분 탐색으로 찾아야 된다고 생각했다.

 

그리고 동시에 두 명 이상이 풍선을 터트리는 경우 A, B, C 순서대로 터트리기 때문에

N번째 풍선을 터트리는 순간의 `-1`초를 해주고 반복문을 돌며 나누어 떨어지는 값을 출력했다.

 

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

public class BOJ32377 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); 

        long[] arr = new long[3]; 
        long max = 0; 

        
        for (int i = 0; i < 3; i++) {
            arr[i] = Long.parseLong(st.nextToken());
            max = Math.max(arr[i], max); 
        }

        long left = 1;
        long right = max * N; 

        
        while (left <= right) {
            long mid = (left + right) / 2;

            long count = 0;
            for (int i = 0; i < 3; i++) {
                count += (mid / arr[i]); 
            }

            if (count >= N) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }

        long preCount = 0;
        for (int i = 0; i < 3; i++) {
            preCount += ((left - 1) / arr[i]);
        }

        for (int i = 0; i < 3; i++) {
            if (left % arr[i] == 0) {
                preCount++;
                if (preCount == N) { 
                    if (i == 0) {
                        System.out.println("A win");
                    } else if (i == 1) {
                        System.out.println("B win");
                    } else {
                        System.out.println("C win");
                    }
                    break;
                }
            }
        }
    }
}