1. 문제파악
- 게임 횟수 : X ( 1 ~ 10억)
- 이긴 게임 횟수 : Y (1 ~ 10억)
- 승률 : Z (소수점 X)
- 게임에서 절대 지지 않는다.
- 게임을 최소 몇 번 더 이겨야 Z가 변하는지 구하시오.
2. 접근 방법
해당 문제는 이분탐색에 퍼센트 계산이 추가된 문제입니다.
1) 이분 탐색
이분 탐색 문제를 풀 때 고려 해야할 사항으로는 다음과 같습니다.
-
이분 탐색의 범위 선정(start, end 값 설정)
-
upper_bound 또는 lower_bound 선정
-
내부적으로 이분 탐색을 나누는 분기 조건 선정
위의 과정으로 해당 문제를 접근해보면, 다음과 같이 정리할 수 있습니다.
범위 선정
승률이 바뀌는 최소 게임 횟수를 구하는 문제이기 때문에, 게임 횟수에 주목해야 합니다.
게임 횟수는 최대 10억회 추가, 최소 0회 추가가 가능합니다.
따라서, start - 0 , end - 1_000_000_000 입니다.
upper_bound & lower_bound 선정
승률이 바뀌는 최소 게임 횟수 이기 때문에, 승률이 변하는 처음 시점에 주목해야 합니다.
따라서, 조건이 성립하는 첫번째 위치(게임 횟수)를 구하는 lower_bound로 구현해야 합니다.
분기 조건 선정
위에서 언급했듯이 승률이 바뀌는지 아닌지에 따라서, 탐색 범위가 변경되는 것을 알 수 있습니다.
예를 들면 다음과 같습니다.
승률이 50% 인 경우, 게임을 진행하면서 50%~100%로 변하게 됩니다.(게임을 절대 지지 않기 때문!)
만약, 승률이 50%인 경우 승률이 커지는 최소의 값을 구할 수 없기 때문에, start 범위를 높여주어 승률이 올라가도록 조정합니다.
그 반대로 승률이 51% 초과한 승률의 경우 최소값이 아니기 때문에, end의 범위를 줄여주어 승률이 내려가도록 조정합니다.
2) 퍼센트 계산
퍼센트 계산은 단순하게 실수형으로 변경한 뒤 100을 곱해주면 될 것 같다고 생각하지만, 이로 인해 필자 또한 많은 오답을 제출했습니다.
해당 계산에서는 자바의 실수 표현 방식이 '부동 소수점' 이라는 점에 주의해야 합니다.
즉, 모든 프로그래밍 언어에서 실수의 표현 방식에서는 오차가 발생하게 됩니다. 정밀도를 높이기 위해서는 결과를 정수형을 요구하는 문제에서는 정수의 형태로 결과를 표현하도록 해주는 것이 제일 좋습니다.
따라서, y의 최댓값 10억, 여기에 100을 곱하면 int 타입의 범위를 초과할 우려가 있기 때문에, long 타입으로 캐스팅 해준 뒤 연산을 수행해주도록 구현했습니다.
3. 구현
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));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken()); // 경기 수
int y = Integer.parseInt(st.nextToken()); // 이긴 횟수
int z = calculatePercent(x, y); // 현재 승률
int min = 0; // 최소 경기 수
int max = 1_000_000_000; // 최대 경기 수
int result = -1; // 승률을 올리기 위한 최소 경기 수
while(min <= max){
int mid = (max + min)/2;
int win_percent = calculatePercent(x+mid, y+mid);
if(win_percent < z){
result = mid;
max = mid - 1;
}
else{
min = mid + 1;
}
}
br.close();
System.out.println(result);
}
static int calculatePercent(int x, int y){
return (int)((long)y * 100 /x);
}
}
