99클럽 코테 스터디 2일차 TIL: 이분 탐색의 범위

오늘의 문제 | 11561. 징검다리

우선 처음 읽었을 때 그리디로 해결해야 하는 생각이 들었다. 정해진 숫자가 없고 머리로는 대충 때려맞춰서 풀 수 있는 문제들은 대체로 그리디인 적이 많았다고 생각했다. 우선 규칙이 이해가 안가는 부분이 있어서 문제부터 꼼꼼히 읽었다.

• 징검다리는 N번까지 있고, 시작점을 아무거나 선택할 수 있음.
• 최대 징검다리 수를 구하는 것으로, 시작하자마자 바로 N번을 밟아버리는 경우의 수인 1번이 최소치임.
• 입력값이 10^16이므로 정상적인 방법으로 해결은 불가능(브루트 포스 불가능)
• 따라서 지난 번처럼 이분 탐색을 이용해야겠다는 생각. 실제로 알고리즘 분류도 이분 탐색. </aside>

아이디어 정리

우선 우리가 찾아야 하는건 최대 횟수이다. 바로 전 점프보다 더 많이 뛰어야 하므로, 시작할 때 1번 뛰고 그다음 2번, 3번 뛰다가… 마지막에 N번 징검다리를 넘기지 않는 선에서 최선의 횟수를 구해야 함.

 

즉, 마지막 점프는 N번에 딱 도착하도록 뛰면 된다는 것.

 

문제에서 N이 10^16까지인 이유를 고려해보면 약간 문제가 있다. 2^16이었으면 최대 숫자가 2^32에 준하는 숫자가 등장하기에 int형에 맞는 범주이겠지만, 최대로 등장하는 10^32가 아닌가? 생각보다 숫자가 너무 커져서 오류가 생길거 같다는 생각이 들었다.

 

수의 범위를 고려하지 않고는 결과가 제대로 나오는지를 확인하기로 했다.

# 정답 코드
for i in range(int(input())):
    n=int(input())

    left=0
    right=n
    mid=1

    while 1:
        if left>=right: break
        mid=(left+right+1)//2
        if (mid**2+mid)//2<n:
            left=mid
        elif (mid**2+mid)//2>n:
            mid-=1
            right=mid
        else: break
    print(mid)
 
 # 오답 코드
 for i in range(int(input())):
    n=int(input())

    left=0
    right=n
    mid=1

    while 1:
        if left>=right-1: break
        mid=(left+right)//2
        if (mid**2+mid)/2<n:
            left=mid
        elif (mid**2+mid)/2>n:
            mid-=1
            right=mid
        else: break
    print(mid)

골 때린다. 어떻게 맞춘건지 감이 잡히지 않는다. 저번 문제처럼 그냥 1 단위로 왔다갔다 해보니까 정답이 나오게 되었다. 어이가 없는 점은 두가지가 있다.

왜 오버플로우가 나지 않았는가?

물론 파이썬이기에 그럴 수 있다. 하지마 그럼에도 숫자가 상당히 커지기에 +1 연산에서 오차가 발생할 수 있을텐데, 왜 오류가 나지 않았는지를 알아보려 한다.

 

long long을 사용할 경우에는 10^16까지는 무리없이 입력 받을 수 있다. 검색해본 결과 unsigned long long을 쓰면 무리없이 C++에서도 해결할 수 있다고 한다. 사실 나는 이분 탐색을 N까지 돌렸지만, 좀만 생각해보면 루트N 근처 정도의 숫자가 최선이라는 사실을 알아낼 수 있다. 그렇다면 mid를 제곱해도 unsigned long long을 넘을 일은 없어보인다.

 

결론: 파이썬이 파이썬했다.

mid값을 구할 때 +1을 하는게 무슨 소용인가

이건 내 if문 로직과 관련이 있을 것으로 보인다. mid를 구할 때 +1을 하게 되면 left와 right의 중간값의 반올림 값으로 구해진다. 그렇다면 원래 오답 코드에서 left와 right를 비교할 때, left가 계속 작은 상황을 방지할 수 있다는게 장점인듯 하다.

 

로직상으로 볼 때, N보다 큰 케이스에서는 정답이 존재할 가능성이 없으므로 right를 mid-1로 갱신해주는데, N보다 작은 케이스에서는 정답이 존재할 수 있으므로 left를 mid로 갱신해주었다. 이 과정에서 left와 right가 1 차이날 경우 생기는 문제를 잡아주는 듯하다.

오늘의 회고

확실히 이분 탐색을 (그것도 숫자를 찾아나설 때) 확실한 근거를 갖고 접근하기는 어렵다고 생각한다. 대략적인 값은 알아낼 수 있으나 이걸 일반화시키기 위한 작업이 오래 걸린다고 느꼈다.

 

그래도 어느 정도 이분 탐색의 감을 잡은 듯하다. 정답을 포함할 수 있는 가능성이 있는가?를 기준으로 범위를 좁혀나가는 방식으로 생각하면 될 듯하다.