99클럽 코테 스터디 2일차 TIL - [이분탐색]

오늘의 문제

 

백준 11561번 (https://www.acmicpc.net/problem/11561)

---

정답 코드

T = int(input())

case = []

for _ in range(T):
    case.append(int(input()))

for N in case:
    l = 1
    r = N
    result = 0

    while l <= r:
        mid = (l + r) // 2
        dist_sum = mid * (mid + 1) // 2  # mid개의 징검다리를 밟았을 때의 누적 거리

        if dist_sum <= N:
            l = mid + 1
            result = mid  # 현재 mid 값이 가능한 징검다리 개수일 수 있음. 값 갱신.
        else:
            r = mid - 1

    print(result)

---

오늘의 회고 & 문제 해설

 

어제에 이어서 다시 등장한 이분탐색 문제였다.

어제 한 번 원리를 파악한 덕에 조금은 빠르게 문제 파악을 할 수 있었다.

오늘 내가 짠 코드는 파이썬이라서 가능한 코드이다. 자바라면 r = 10**16 으로 초기부터 설정해주어야 한다고 한다.

파이썬이라 다행이다... 만세! 🙌 🙌

 

Start point = 0, End point = N (input으로 주어지는 총 다리의 수) 으로 잡는다.

이 때, N의 최대 범위가 10^16 이기 때문에, 이진탐색 없이는 시간초과가 뜰 수밖에 없다.

 

이진탐색을 했을 때 계산의 시간복잡도를 어마어마하게 낮출 수 있는데, 어느 정도냐면...

10^3 = 1000 이고, 2^10 = 1024 이므로, 대략 이 둘을 비슷한 크기라고 생각을 해보자.

그러면 10^9 = 10억 이고, 이 숫자가 대략 2^30 과 비슷하다고 생각했을 때, 이진탐색을 하는 경우 log2(2)^30 수준으로 낮아진다.

다시 말해서, 그냥 하면 10억번 계산할 식을 이진탐색을 수행하면 30번 만에 끝낸다는 말이다...!

마찬가지로, 10^12 = 1조 라서 대략 2^40 이므로, 이진탐색으로 계산을 하면 40번만에 계산이 끝날 수 있다.

이진탐색의 위대함이 확 체감이 되는 숫자이다...! 😲👏👏👏

---

이진 탐색 반복문 (while l <= r)

• mid 값을 l과 r의 중간 지점으로 설정한다.
• dist_sum = mid * (mid + 1) // 2를 계산한다. 이는 1부터 mid까지 징검다리를 밟았을 때의 누적 거리와 같다.

조건문

• dist_sum <= N인 경우! N 이하이므로 현재 mid 값이 가능함을 의미한다.
  • l = mid + 1로 설정하여 더 큰 mid 값을 탐색해본다.
  • result를 mid로 갱신하여 최대 mid 값을 저장한다.
• dist_sum > N인 경우! 거리가 초과했으므로 r = mid - 1로 설정하여 더 작은 mid 값을 찾아본다.

결과 출력

• 각 테스트 케이스마다 최종 result 값을 출력하여, N을 넘지 않는 최대 징검다리 개수를 출력한다.