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

오늘의 학습 키워드

• 이분탐색
• 백준 11561번 징검다리

공부한 내용

문제의 핵심

• 각 점프마다 이전 점프보다 최소 1 이상 긴 거리를 뛰어야 함
• 마지막 N번 징검다리는 반드시 밟아야 함
• 최대한 많은 징검다리를 밟는 것이 목표

해결 방법

• 이분탐색을 통해 가능한 최대 점프 횟수를 찾음
• k번 점프할 때 필요한 최소 거리는 1 + 2 + 3 + ... + k = k(k+1)/2
• 이 거리가 N보다 작거나 같아야 하며, N번 징검다리까지 도달 가능해야 함

코드 원리

• start와 end로 탐색 범위 설정
• mid값으로 가능한 점프 횟수 계산
• 등차수열의 합 공식 활용하여 필요한 최소 거리 계산
• 이분탐색으로 최적값 도출

정답 코드

T = int(input())

for _ in range(T):
    N = int(input())
    start = 0
    end = 10**9

while start < end:
    mid = (start + end) // 2
    if mid * (mid + 1) // 2 <= N:
        start = mid + 1
    else:
        end = mid
print(start - 1)

오늘의 회고

• 이분 탐색이 습관처럼 생각나지 않아서 단순히 구현하였고, 시간 초과 문제를 직면하였음. 시간 초과를 보고 나서야 1일차 배웠던 것처럼 이분탐색이라는게 생각났음.
• 큰 수가 등장할 때는 이분탐색을 항상 고려하고 적용할 수 있도록 하자.