[백준] 1072 - 게임

문제

백준 1072번 게임

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

 

 

문제 풀이

이 문제는 추가 게임을 하면 반드시 이긴다는 가정 하에, 현 상태에서 승률이 일의 자리 이상 변화하는 최소 추가 게임 횟수를 구하는 것이 목적이다. 

 

1. 산술 연산

구하고자 하는 횟수를 a 라고 했을 때, a는 다음과 같은 부등식을 만족한다. 

이때, a 값은 자연수이며,  이미 승률이 100 혹은 99인 경우에는 승률이 변하지 않으며 부등식을 적용할 수 없다. 따라서 z 값이 98 이하인 경우에 아래의 부등식을 적용후 정수 a의 최소값을 구하여 출력한다.

 

2. 이분 탐색

산술 연산의 방법으로 문제를 푼 후 해당 문제의 알고리즘 분류를 확인하고, 다른 사람들의 풀이를 찾아보니 '이분 탐색'으로 해결할 수 있는 문제라고 설명되어 있어 해당 알고리즘으로 다시 풀어보았다. 

 

이분 탐색은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 리스트의 시작과 끝 값의 중간 값을 찾고자 하는 값(target)과 비교한 후, 중간 값 > target 이면 끝 값을 현재의 중간 값(중간값 - 1 로 한다)으로 둔 후 해당 범위에서 다시 target 값을 비교한다. 중간값 < target이면 시작 값을 현재의 중간 값(중간값 + 1 로 한다)으로 두어 비교 과정을 반복 수행하는 알고리즘이다.

 

이분 탐색은 '정해진 범위에서 특정 조건을 만족하는 값(혹은 최솟값/최댓값)을 찾고자 할 때' 많이 사용된다. 이 문제는 승률이 달라지는지(높아지는지) 여부를 통해 게임 횟수의 최솟값을 찾는 문제이다. 게임 횟수를 변수로 두었을 때, 승률의 변화 유무를 조건으로 하여 이분 탐색을 통해 조건을 만족하는 횟수의 최소값을 빠르게 찾을 수 있다. 

이분 탐색은 시간 복잡도 O(log(N))으로 매우 빠른 속도를 가지며, 실제 백준 테스트에서도 단순한 산술 연산과 동일한 실행 시간을 나타내고 있다. 

 

 

 

코드

# 산술 연산
import sys, math

input = sys.stdin.readline

x,y=map(int,input().split(' '))

current= int(y*100/x)
if current in [100,99]:
  ans=-1
else:
  ans= math.ceil(((current+1)*x-100*y)/(100-current-1))
print(ans)

 

# 이진 탐색
x,y=map(int,input().split(' '))
z=int(y*100/x)

# 승률이 변하는지 확인
def check(i):
  cand=int((y+i)*100/(x+i))
  return True if cand>z else False


# 변수는 추가 게임 횟수
# start와 end는 0과 x
start,end=1,x
ans=-1
while start<=end:
  mid=(start+end)//2
  if check(mid):
    ans=mid
    end=mid-1
  else:
    start=mid+1

print(ans)