백준 11561 징검다리

https://www.acmicpc.net/problem/11561

11561번: 징검다리

brute force/완전 탐색은 모든 경우의 수를 전부 따져보는 것을 말한다. 여러 알고리즘은 이러한 모든 경우의 수 중에서 확정적으로 들어낼 수 있는 부분을 걸러준다. 이분탐색은 답이 아니라고 확신하는 부분을 절반씩 들어내기에 빠르게 완탐(?!)이 가능해진다. 혹시나 이분탐색이 생소하다면 이 포스팅을 참조 부탁드린다. 

이 문제는 왜 이분탐색으로 풀 수 있을까? 주어진 징검다리의 상한값이 1e16으로 너무너무 커서? 그것도 한가지 힌트가 되겠지만, 문제를 잘 생각해보면, 가장 많은 징검다리를 밟는 방법이 정해져있기 때문이다. 바로 1+2+3+4+5+...이런식으로 밟는 경우이다.

 

즉, 초기값이 1이고 차이가 1인 등차수열의 합으로 징검다리 총 수를 만들어내면 된다.

만약에 (m개의 돌을 사용하는) 등차수열의 합이 주어진 징검다리 총 수보다 모자라다면, 마지막 m번째 돌을 아주 넓게 점프하여 마지막 돌을 밟을 수 있다. 하지만 총 수보다 크다면, 마지막 돌을 밟을 수 없다. 

몇 개의 돌을 밟느냐에 따라 아우를 수 있는 징검다리 총 수의 증가/감소 방식이 일정한 경향을 갖기에 이분탐색 로직을 만들 수 있다. 

 

이제 상한값을 몇으로 놓을지에 대해 잠깐 생각해보자. 단순히 엄청나게 큰 값을 넣어도 문제가 되지 않는다. 하지만 조금만 더 생각해보자.

등차수열의 합을 구하는 공식 n(n+1)/2=징검다리 총 수의 상한값 1e16 가 된다.

이는 n^2 + n - 2*(1e16) = 0 이라는 2차 방정식의 형태로 정리된다. 이제 근의 공식으로 n을 구할 수 있다! (n은 양수임에 주의)

 

<주요 내용>

이분탐색, 2차 방정식, 근의 공식

 

<코드>

Python

import sys
from math import sqrt
si = sys.stdin.readline

c = -2*int(1e16)
mx = int((-1+sqrt(1-4*c))//2)+1

t = int(si())
while t:
    t -= 1
    n = int(si())
    s, e, ans = 0, mx, 0
    while s < e:
        mid = (s+e)//2
        if (mid+1)*mid//2 <= n:
            ans = mid
            s = mid+1
        else:
            e = mid
    print(ans)