성능 요약
메모리: 113112 KB, 시간: 112 ms
분류
이분 탐색(binary_search), 수학(math)
문제 설명
김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.
이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.
게임 기록은 다음과 같이 생겼다.
- 게임 횟수 : X
- 이긴 게임 : Y (Z%)
- Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.
X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.
입력
각 줄에 정수 X와 Y가 주어진다.
출력
첫째 줄에 형택이가 게임을 최소 몇 판 더 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.
풀이 과정
실버 3 문제라 쉬울 거라 생각했고, 단순 구현 문제라 생각했다.
X의 범위는 1,000,000,000(10억)이고, 시간 제한은 2초라서 2억번 정도까지 탐색이 가능할 것이라 생각했다.
그래서 처음에 생각한 풀이는 어차피 승률 1%가 올라가려면, X의 1%는 무조건 올라가야 한다 생각해서 X와 Y에 X의 1%를 먼저 더한 뒤에 완전 탐색을 진행했다.
그러면 X가 10억일 때 1억번을 이미 계산해주는 것이니 시간 초과에 걸리지 않을 것이라 생각했다.
하지만 당연하게도 이 풀이는 틀렸다 .. ^^
1.99% -> 2.00% 일 경우에는 위 전제가 성립이 안되기 때문이다.
그래서 다른 방법을 생각해보려 했는데, 수업 가기 전까지 풀이를 생각해내지 못 해 결국 다른 사람의 풀이를 보고 아이디어를 얻었다.
이분탐색을 이용하는 것 이었다....
이렇게 되면 O(logN)으로 10억개라도 30번의 탐색만으로 답을 찾을 수 있게된다.
너무 당연한 것이었는데, 아직 코딩테스트 실력이 먼 것 같다.
문제만 보고 바로 풀이를 알 수 있도록 더 열심히 해야겠다.
코드
import sys
X, Y = map(int, sys.stdin.readline().split())
Z = (100 * Y) // X
if Z == 100 or Z == 99 :
print(-1)
exit()
cnt = 0
left = 1
right = X
while left <= right :
print(cnt)
mid = (left + right) // 2
if ((Y + mid) * 100) // (X + mid) <= Z :
left = mid + 1
else :
cnt = mid
right = mid -1
print(cnt)