1072번: 게임
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시
www.acmicpc.net
의식의 흐름
(게임을 더하면 이긴 게임(Y)만 늘어나는게 아니라 게임 횟수(X)도 늘어나는걸 생각 못하고,,,) 1~X-Y번 이분 탐색 돌리면 되겠네 라고 했다가 7번의 "틀렸습니다"를 보고 정신차림. 혹시나 하고 end = X로 고쳤더니 바로 통과해버렸당. 근데 아직까지 왜 end = X인지 이유를 명확히 모르겠다👻
풀이
1. Z가 99%인 경우, 게임을 아무리 해도 승률이 100%가 되지 못하므로 해당 경우는 바로 처리
2. 99% 아래인 경우, 이분 탐색 시작.
코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
long X = Long.parseLong(st.nextToken()); // 게임 횟수
long Y = Long.parseLong(st.nextToken()); // 이긴 게임
long Z = (Y*100)/X; // 승률
if(Z>=99){ // 99% 이상은 아무리 게임해도 승률 변동 X
bw.write("-1");
}
else{
long start = 1;
long end = X;
while(start<=end){
long mid = (start+end)/2;
long newZ = (mid+Y)*100/(mid+X);
if(newZ>Z){
end = mid - 1;
}
else
start = mid + 1;
}
bw.write(Long.toString(start));
}
bw.flush();
}
}
'알고리즘 > 백준' 카테고리의 다른 글
[JAVA] 백준 q11003 - 최솟값 찾기 (0) | 2023.08.08 |
---|---|
[JAVA] 백준 q17276 - 배열 돌리기 (0) | 2023.06.22 |
[JAVA] 백준 q1253 - 좋다 (1) | 2023.06.10 |
[JAVA] 백준 q11659 - 구간 합 구하기 4 (0) | 2023.06.10 |
[JAVA] 백준 q16953 - A → B (0) | 2023.05.01 |