99클럽 코테 스터디 1일차 TIL: 브루트포스와 이분 탐색

오늘의 문제 | 1072. 게임

X의 범위가 10억이기는 하지만, 숫자가 변하기 위한 조건을 생각했을 때 천만번 정도의 실행이면 충분히 도전해볼만 하다는 생각에 브루트포스로 접근하기 시작했다.

 

핵심 아이디어

만약 Z가 99나 100일 경우, 이 숫자는 절대 변할 수 없다. 99%나 100%에서는 더이상 커질 수 없다는 생각이다. 따라서 Z가 99나 100이 나왔을 경우에는 바로 -1을 출력하도록 했다.

 

하지만 틀렸다… 시간초과가 아니라 틀렸다는게 이해가 안가긴 했다. 도저히 틀릴 가능성이 없어보이는데 틀린 걸로 보아, 실수 오차의 가능성을 생각했다.

# 기존 Z를 구하는 식
Z=int(Y/X*100)

# 실수 오차를 최소화하기 위한 식
Z=int((Y*100)/X)

결국 정답을 맞췄다! 테스트에서 2초가 나오길래 틀릴 줄 알았지만 확실히 연산 횟수가 1억 번을 넘지 않다보니 시간 초과는 안나온 듯 하다.

# 정답 코드
X,Y=map(int,input().split())
Z=int((Y*100)/X)
count=0
if Z>=99: print(-1)
else:
    while 1:
        X+=1
        Y+=1
        count+=1
        if int((Y*100)/X)!=Z:
            print(count)
            break

하지만 이 문제가 실버3인게 단순히 실수 때문은 아닐거라 생각해서 알고리즘을 확인했다.

역시나 알고리즘이 브루트포스가 아닌 이분 탐색이었다. 이 문제를 이분 탐색으로 어떻게 풀 수 있을지를 알아보기로 했다. 단순한 이분 탐색은 아닐 거라는 생각이 든다. 각 케이스의 최악의 경우로부터 현재까지를 각각 left와 right로 두고 좁혀가며 찾아보면 어떨까라는 생각이 든다.

 

테스트1: 최악의 경우를 생각해내자.

우선 X의 최댓값은 10억이다. 이때 Y가 9.8억일 경우, Z값을 99로 만들기 위한 최대 실행횟수는 정답 코드로 실행시켜봤을 때 시간 초과가 난다… 그래도 단순 추측으로 10억번 가량 실행시켰을 경우에는 문제없이 작동한다.

 

(X가 20억, Y가 19.8억이 되므로 99가 된다는 것을 알 수 있다. 즉 최악의 상황은 10억번 실행시켜야 됐던 것.)

 

그럼 우리는 변화량을 R로 두고, R의 범위를 1에서 10억 사이에서 확정지을 이분 탐색 알고리즘을 구현하면 되는 것이다. 아까처럼 Z가 99 이상일 때는 예외처리 하고 구해보려 한다.

X,Y=map(int,input().split())
Z=int((Y*100)/X)

left=1
right=1_000_000_000

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

이렇게 구현했을 때 몇몇 문제가 잘못 출력된다는 것을 확인했다. 모두 1차이로 틀렸다고 나온다. 아무래도 break 조건이나 left, right 세팅에서 잘못된 부분이 있어보인다.

 

일부 케이스에서만 1차이가 난다는 것은, left right 중 하나의 값을 실제로 설정하는 값과 출력하는 mid 값이 달라서 생긴 문제일 것이다.

따라서 left에 mid+1을 더하는 것이 아닌, 이미 mid에 1을 더하고, 해당 값을 left로 설정하는 순으로 하면 문제가 안생기지 않을까 생각이 들었다.

 

이렇게 실행했을 때 가장 느린 케이스가 20ms일 정도로 시간을 획기적으로 단축시켰다.

X,Y=map(int,input().split())
Z=int((Y*100)/X)

left=1
right=1_000_000_000

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

---

오늘의 학습 키워드: 브루트포스와 이분 탐색

결국 이분 탐색이 나오게 된 배경을 생각해보면, 모든 케이스를 하나하나 확인할 수 없기에 획기적으로 시간을 단축시킬 수 있는 방법으로 제시된 것이다. 사실 시간 복잡도 측면에서도 이분 탐색은 logN이기 때문에 선형 시간이 걸리는 브루트포스보다 압도적으로 빠를 수밖에 없긴하다. 평소에 이분 탐색을 보면 조금 두려워서 다른 방식으로 풀려고 하는 경향이 있는데, 이젠 이분 탐색도 어느정도 시도해볼만 하다는 생각이 든다.