[99클럽 코테 스터디 TIL#1일차] 백준 1072

문제

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

 

 

문제 풀기

 

1. 알고리즘 사용

  1) 이분 탐색

 count를 하나씩 증가시키면서 값을 찾으면 시간 초과, 필요 이상으로 많은 반복 발생한다. 따라서 이 문제에 이분 탐색을 활용하면 최소, 최대 값을 찾을 때 시간 복잡도를 줄일 수 있다. 가능한 범위를 설정하고 이분 탐색으로 좁혀가면서 계산했다.

 

  2) 이분 탐색 검색 공간 설정

 

 

2. 다항식 사용

  1) 확률

 현재 승률(z) = ((y + a) * 100) / (x + a)로 계산할 때, (여기서 x는 총 경기 수, y는 승리 횟수) 승률을 99%에서 100%로 올리려면 y / x 비율을 아주 미세하게 증가시켜야한다. 이 말은 추가로 몇 번을 더 이겨도 승률이 100%로 쉽게 올라가지 않는다는 것이다.

 

  2) 다항식

 승률이 변하는 최소값을 구하면 되니 아래의 다항식을 풀면 된다.

 

  현재 승률(z) + 1 = ((y + a) * 100) / (x + a)

 

 

 

작성한 코드

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        int percent = (int)((long)y * 100 / x);
        
        if(percent >= 99) {
            System.out.println(-1);
            return;
        }
        
        int left = 1;
        int right = x;
        int result = 0;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            int newPercent = (int)((long)(y + mid) * 100 / (x + mid));
            
            if(newPercent > percent) {
                result = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
       
        System.out.println(result);
    }
}