[백준] 1072 게임

J. Hwang·2024년 10월 28일

coding test

목록 보기

28/108

문제

김형택은 지금 몰래 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 = map(int, input().split())
Z = int(Y/X*100)

i = 1
while True:
    new_z = int((Y+i)/(X+i)*100)
    if new_z > Z:
        print(i)
        break
    elif X == Y:
        print(-1)
        break
    else:
        pass
    i += 1

처음 풀이는 위와 같이 풀어서 시간 초과가 떴다. 알고리즘에 대한 이해 없이 그저 "동작"하도록 구현한 것이 문제였다.
아래는 reference를 보고 수정해서 정답을 받은 코드이다. (설명은 아래 코멘트 참조)

X, Y = map(int, input().split())
#Z = int(Y/X*100)   -> 파이썬 부동소수점 오차 이슈 때문에 이 코드는 계속 오답을 반환...
Z = (Y*100)//X 

left = 1
right = X
answer = X     # (자연수) 승률이 바뀌기 위해 플레이해야 할 게임의 최소 횟수

if Z >= 99:
	print(-1)
else:
	while left <= right:
		mid = int((left + right)/2)
		new_z = int((Y+mid)/(X+mid)*100)
		if new_z > Z:
			answer = mid
			right = mid -1
		else:
			left = mid + 1
	print(answer)

코멘트

이 문제의 유형은 이진 탐색 (binary search) 이다.
나의 첫 풀이도 옳은 답 자체는 내놓는다. 그렇게 기능하도록 직관적으로 구현했으니까.
그런데 X가 커질수록, 특히 제한에서 그 범위를 알 수 있듯이 연산이 굉장히 비효율적으로 되어서 시간 초과라는 실패 결과를 내놓을 수 밖에 없다.
이 때 이진 탐색을 이용하면 보다 효율적인 구현이 가능해진다. 이진 탐색이란, 원하는 조건의 요소를 찾을 때까지 탐색 범위를 절반씩 줄이는 알고리즘이다.
1부터 끝까지 모든 숫자를 훑어서 비효율적인 나의 첫 풀이와 달리, 이진 탐색은 탐색 범위를 줄여나가며 효율적인 시간 복잡도를 갖게 되는 것이다.
이진 탐색을 구현하기 위해서는 (오름차순 (경우에 따라 내림차순)으로 정렬한 후에) 왼쪽 맨 끝인 left와 오른쪽 맨 끝인 right를 설정한 후 중간 값 mid = (left + right) //2 을 이용하여 특정 조건을 만족하는지와 같이 구현하면 된다.

여전히 이 문제에서 이해가 안 되는 부분은, "왜 answer의 최대값이 X인 것일까?"