[백준 11561] 징검다리

문제

승택이는 강을 건너려 한다.

승택이는 수영을 못하기 때문에, 강에 놓인 징검다리를 밟고 건너갈 것이다.

승택이는 수영은 못하지만 제자리뛰기는 정말 잘한다. 원하는 어느 곳으로든지 점프해서 바로 갈 수가 있다.

승택이는 이제 강의 한쪽 변 앞에 서 있다.

강엔 1번부터 시작해 2번, 3번, ... , N번 징검다리가 차례대로 놓여 있다.

강의 폭이 넓은 탓에 징검다리의 수는 엄청나게 많다.

이 징검다리를 모두 밟고 싶지는 않았던 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만을 밟고 가기로 했다.

물론 강 건너편으로 바로 점프하는 것도 가능하지만, 더 재미있게 강을 건너기 위해 승택이는 다음과 같은 규칙을 정했다.

1. 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다.
2. 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
3. N번 징검다리는 반드시 밟아야 한다.
4. N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.

승택이가 위의 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?

입력

첫째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 정수 한 개로 이루어져 있으며, 징검다리의 총 수 N을 의미한다. (1 ≤ N ≤ 10^16)

출력

 

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

 

---

풀이

먼저, 밟을 수 있는 징검다리의 최대 수를 구하려면 첫 점프를 한 칸 뛸 것이다

그래야 1칸 점프, 2칸 점프, 3칸 점프 와 같이 규칙을 준수하며 이전 점프보다 1이상 긴 거리를 뛸 테니깐 말이다

 

쉽게 말해 1+2+3+4+... 값을 하나씩 증가시켜주며 더하다가 합이 N이 넘지 않는 마지막 수를 구하면 밟을 수 있는 최대 수가 될 것이다

 

하지만 입력값의 범위를 보면 10^16, N의 최대값은 1경이다

O(logN) 으로 해결해야하기에 이분탐색 (매개변수탐색) 풀이로 접근해보았다

 

N=100 일 경우,

절반으로 나눈 50으로 => 1~50의 합 (1씩 증가시키며 점프한 거리) + 51 (다음 점프거리)를 계산하고 N과 비교한다

N보다 작은 경우 (50 + 100) // 2 = 75로 계산 및 비교

N보다 큰 경우 (0 + 50) // 2 = 25로 계산 및 비교

 

즉, 수를 절반씩 잘라가며 대입하여 비교하면 된다

 

# 징검다리
import sys
input = sys.stdin.readline

for _ in range(int(input())):
    N = int(input())
    l,r = 0,N
    while l <= r:
        m = (l + r) // 2
        if ((m*(m+1)//2) + (m+1)) > N:
            r = m-1
        else:
            l = m+1
    print(l)

 

 

실버 3 문제임에도 난이도와 유형을 가려놓고 풀어보니 꽤나 생각하게 만들었던 문제였다