99클럽 코테 스터디 1일차 TIL / 이분 탐색

✏️ 문제

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

 

• 게임 횟수 : X
• 이긴 게임 : Y (Z%)
• Z는 형택이의 승률이고, 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z=88이다.

 

X와 Y가 주어졌을 때, 형택이가 게임을 최소 몇 번 더 해야 Z가 변하는지 구하는 프로그램을 작성하시오.

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S3

✅ 소요 시간: 1시간 45분

✅ 권장 시간: 45분

 

💡 풀이

1) 문제 유형 파악

자력으로 이분 탐색 유형인 걸 안 건 아니고, 백준에서 제공하는 '알고리즘 분류'를 통해 이분 탐색 유형인 걸 확인한 후 풀이에 들어갔다. 내일부터는 5~10분 정도 문제 유형이 뭔지 스스로 고민해 본 후에 문제를 풀어야겠다.

 

풀다 보니까 [BOJ] 2003번: 수들의 합 2 문제와 비슷한 것 같기도 한 느낌을 받았다.

 

2) 아이디어

① 이분 탐색 유형이기 때문에 가장 먼저 든 생각은 start/end/mid 변수를 써야겠다고 생각했다. 이 때 'mid' 변수의 값은 (start+end)/2이다.

 

② start 변수의 초기값은 1로 잡고 end 변수의 초기값은 X의 제한 값보다 1 큰 값으로 잡았다. end 변수의 초기값을 이렇게 잡은 건 내 습관(제한 범위보다 여유롭게 설정하는 것)이라 큰 이유가 있는 것은 아니다.

 

③ ⭐핵심⭐

새로 구한 Z 값과 기존의 Z 값을 비교해서 승률의 변화를 추적하는 부분이 이 문제와 이분 탐색 유형의 핵심이라고 생각한다.

 

새로운 Z 값이 기존 Z 값보다 클 경우: 최소 게임 수는 mid 값이 되고, 계속해서 작은 값을 찾아가야 하기 때문에 end 범위를 mid-1로 갱신해 탐색 범위를 줄여주었다.

 

새로운 Z 값이 기존 Z 값보다 작을 경우: 내가 손으로 직접 계산해 본 몇 가지 예시에서는 게임 횟수가 늘면 Z 값이 작아지는 경우는 없었지만 단순히 내가 발견하지 못한 것일수도 있기 때문에 start를 mid+1로 갱신해 탐색 시작점을 변경해주었다.

 

④ 마지막으로 처리해줄 부분은 -1을 출력해야 하는 경우이다. 최소 게임 횟수를 저장할 변수 min_game의 초기값을 매우 큰 값으로 설정했기 때문에 이 값이 바뀌지 않고 초기값과 똑같은 상태일 때 -1을 출력하도록 했다.

 

3) 구현

import sys

input = sys.stdin.readline

# X: 게임 횟수, Y: 이긴 게임, Z: Y/X
X, Y = map(int, input().split())

Z = (Y*100)//X

start = 1
end = 1000000001

min_game = float("inf")

while start <= end:
    mid = (start+end)//2
    
    new_Z = ((Y+mid)*100)//(X+mid)

    if new_Z > Z:
        min_game = mid
        end = mid-1
        
        answer = min_game
    else:
        start = mid+1
    
if min_game == float("inf"):
    print(-1)
else:
    print(answer)

 

4) 배운 점/궁금한 점

❗ 배운 점

• start, end 변수를 내가 원하는 방향으로 움직이면서 이분 탐색 유형 문제에 활용하는 법