[백준 알고리즘]1072번: 게임_Java

[문제]

김형택은 지금 몰래 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

​

[예제]

---

>문제 풀이

 

>문제 이해

게임횟수: X

이긴 게임: Y(Z%)

Z는 형택이의 승률, 소수점은 버린다.

ex) X=53, Y=47 → Z =47/53*100=88.xx → 88

​

input))

X(10억이하), Y

​

output))

형택이가 최소 몇판을 더 해야하는지 출력

단, 만약 Z가 절대 변하지 않는다면 -1 출력

---

>문제 풀이

절대 Z가 변하지 않는 경우는??

1) 일단, Z가 100이면 101%로 올라갈 수 없다.

2) Z가 99이면? 이미 전적에 패배가 있기 때문에 몇경기를 더 이기든 100%로 올라갈 수 없다.

​

위의 경우를 제외하고는 탐색을 하면되는데

우리가 구하려고 하는 값을 answer라고 할때 answer=1~X까지의 수이다.

- 왜?)) 최소 한 경기 이상은 해야 승률이 오를것이고

Z가 98%의 경우 (98+100)/200*100=99퍼로 확률이 올라가기 때문이다.

​

이제 어떤 방법으로 탐색을 할지 정해야한다.

1~X까지 탐색을 하려면 최악의 경우 10억번을 탐색해야한다. (시간복잡도 O(N))

그러나 이분탐색을 하게 된다면 O(logN) 만에 탐색이 가능하다.

​

여기까지 왔다면 이분탐색을 구현하면되는데

나는 1) while의 조건문과 (left<=right) (left<right)

2) left=mid+1;, right= mid-1인가 mid로 해야되나 여기서 헷갈렸다..

​

이전에 이분탐색 할 때도 헷갈렸었는데, 왜 그렇게 되는지 확실히 인지하지 못한채 넘겼어서 그런 것 같다.

1)번의 경우 Z=98일 때는 위에 설명했던 것 처럼 left를 쭉쭉 올려서 right까지 가야하는데 mid=(left+right)/2로 계산하기 때문에 mid에 right값도 들어가려면 left==right일 때도 고려를 해야하기 때문이다.

그래서 left<=right 여야 한다. (코드에 따라 다를 수 있음)

​

2)번의 경우

초기값 설정할 때도 left=1, right=X로 mid로 올수 있는 값들의 범위를 설정해준거나 다름 없기 때문에 while안에서 left, right 값을 조정할 때도 mid가 올 수 있는 값만 고려해주면 된다.

mid로 계산했을 때 확률이 Z보다 높으면 다음에 고려할 값은 mid 아래의 값들만 고려해주면 되기 때문에 right=mid-1로 조정해주면 된다.

 

>전체 코드

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;

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());
		
		long answer=-1;
		long X= Long.parseLong(st.nextToken());
		long Y= Long.parseLong(st.nextToken());
		int Z= (int)(Y*100/X);
		
		//Z==100: 100퍼에서 101퍼로 못올림
		//Z==99: 전적에 이미 패가 있기 때문에 어떤 방법을 써도 100퍼는 못만든다.
		//이분탐색 logN
		long left=1, right=X, mid=0;
		int nZ;
		while(left<=right) {
			if(Z>=99) {
				answer=-1;
				break;
			}
			mid= (left+right)/2;
			nZ= (int)((Y+mid)*100/(X+mid));
			if(nZ<=Z) {
				left=mid+1;
			}else {
				answer= mid;
				right=mid-1;
			}
		}
		System.out.println(answer);
	}//main
}

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

1072번: 게임