B1072-게임
| 날짜 | 2024-04-06 |
| 사용 언어 | Java |
| 문제 유형 | #binary_search#Math |
| 문제 URL | https://www.acmicpc.net/problem/1072 |
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 45442 | 10802 | 8094 | 24.315% |
문제 #
문제 설명 #
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.
이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.
게임 기록은 다음과 같이 생겼다.
- 게임 횟수 : X
- 이긴 게임 : Y (Z%)
- Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.
X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.
제한사항 #
-
각 줄에 정수 X와 Y가 주어진다.
-
첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.
-
1 ≤ X ≤ 1,000,000,000
-
0 ≤ Y ≤ X
나의 풀이 #
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
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());
br.close();
// 1 ≤ X ≤ 1,000,000,000
long X = Long.parseLong(st.nextToken());
// 0 ≤ Y ≤ 1,000,000,000
long Y = Long.parseLong(st.nextToken());
// 승률이 99%면 앞으로 승률을 100%로 올릴 수 없다.
long count = -1;
if ((100 * Y) / X < 99) {
count = binarySearch(X, Y);
}
System.out.println(count);
}
private static long binarySearch(long X, long Y) {
long start = 0; // 최소 게임 횟수
long end = 1000000000; // 최대 게임 횟수
long currentRate = (100 * Y) / X;
while (start <= end) {
long mid = (start + end) / 2;
// 추가로 mid 만큼 이길 때의 승률
long addWinRate = (100 * (Y + mid)) / (X + mid);
// 승률이 오르지 않았을 경우
if (addWinRate - currentRate < 1) {
// 이긴 횟수가 더 많아져야 함
start = mid + 1;
} else {
end = mid - 1;
}
}
return start;
}
}
다른 사람의 풀이 #