[백준] 11561 징검다리

문제

승택이는 강을 건너려 한다.
승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.
승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.
승택이는 이제 강의 한쪽 변 앞에 서 있다.
강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.
강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.
이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.
물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.
첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
N번 징검다리는 반드시 밟아야 한다.
N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.
승택이가 위의 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 정수 한 개로 이루어져 있으며, 징검다리의 총 수 N을 의미한다. (1 ≤ N ≤ $10^{16}$)

출력

각 테스트 케이스마다 한 줄에 승택이가 밟을 수 있는 최대 징검다리 수를 출력한다.

내 풀이

input1 = int(input())

for a in range(input1):
    stones = int(input())
    sum1 = 0
    i = 0
    while True:
        i += 1
        sum1 += i
        if sum1 > stones:
            break
    print(i-1)

처음에 위와 같이 풀었다가 역시나 시간 초과로 실패했다. 가장 많은 징검다리를 밟아야 한다는 점에서 이전에 푼 백준 1789 수들의 합 문제와 같은 방법으로 풀었는데 여기에서도 N이 최대 $10^{16}$ 까지 커질 수 있는 만큼 시간 복잡도를 고려하지 않으면 실패하게 된다.

아래는 오답풀이 하여 다시 제출하고 정답을 받은 코드 (설명은 아래 코멘트에서)

input1 = int(input())

for a in range(input1):
    stones = int(input())
    answer = 0
    left = 1
    right = stones
    while left <= right:
        mid = (left + right)//2
        if ((mid+1)*mid)//2 <= stones:
            left = mid + 1
            answer = mid
        else:
            right = mid - 1
    print(answer)

코멘트

이 문제도 백준 1072 게임과 같은 이진 탐색 유형이다. 이진 탐색 알고리즘을 활용할 뿐만 아니라 이 문제에서는 등차수열을 활용해서 풀 수 있어야 한다. 처음에 캐치했듯이 가장 많은 징검다리를 밟기 위해서는 1+2+3+4+....+n 번을 밟아야 한다.
이렇게 1, 2, 3, 4, ... 와 같이 같은 차이 (→ 공차) 만큼 떨어진 수의 나열을 등차수열이라고 하는데, 이번 문제에서는 공차가 1인 경우에 해당한다. Reference에 따르면, 등차 수열의 합은 $S_{n}$ = $\frac{ n( a_1 + a_n )}{2}$ 과 같이 표현되고, $a_n$ = $a_1$ + $(n-1)d$ ($d$ = 공차 = 1) 이므로, 이번 경우에 맞게 식을 정리하면 $S_n = \frac{n(n+1)}{2}$ 이 된다.
따라서 $S_n$을 1부터 n까지 무작정 더했던 이전 풀이와 달리, $S_n$ = mid(mid +1)/2 로 설정하여 이 값이 징검다리 개수보다 큰 지 작은지를 판별하고, left와 right를 조정하는 방식으로 이진 탐색을 진행하면 되는 것이다.
수열과 이진 탐색을 잘 활용하는 문제인 듯하여, 여러 번 다시 풀어볼 수 있도록 해야겠다.

References

https://www.acmicpc.net/problem/11561
https://blog.naver.com/jamduino/220959928433
https://hyeonlogforweb.tistory.com/76