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

✏️ 문제

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

 

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

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

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

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

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

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

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

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

 

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

 

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

 

🤖 입출력 예시

 

🧐 난이도/소요 시간

✅ 난이도: solved.ac 기준 S3

✅ 소요 시간: 1시간 50분

✅ 권장 시간: 45분

 

💡 풀이

1) 문제 유형 파악

어제 결심한대로 문제를 보고 나서 10분 동안 문제 유형에 대해 고민했다.

 

처음에는 입출력 형식이 뭔가 DP스럽다고 생각했는데 아무리 DP로 풀어도 10^16 범위를 처리할 수가 있나? 싶었다. 하지만 아쉽게도 여기서 이분 탐색을 써야겠다는 생각으로 이어지지는 못했고, 그럼 뭐 써야 하지? 하는 중에 10분이 초과해서 알고리즘 분류를 통해 아 이분 탐색이구나 하는 걸 알게 됐다.

 

2) 아이디어 흐름

① ⭐핵심 (1)⭐

'어떻게 해야 징검다리를 최대로 밟을 수 있을까?'라는 의문에 대해 내가 내린 결론은 '조금씩만 점프하는 것'이다.

 

문제에 적힌 표현을 활용해 다시 적어보자면 '이전에 점프한 거리보다 딱 1만큼만 더 길게 점프'해야만 밟는 징검다리 수를 최대로 만들 수 있다.

 

② ⭐핵심 (2)⭐

이분 탐색 문제는 start, end 범위를 조절하기 위한 조건이 필요한데 '점프 거리 누적 합' 개념과 핵심 (1)의 내용을 가지고 이 문제에서 필요한 조건을 도출할 수 있다.

점프 거리 누적 합 = 첫 번째 점프 거리+두 번째 점프 거리+...+K번째 점프 거리

 

결국 N번째 징검다리는 무조건 밟으면서 최대 징검다리를 밟을 수 있는 점프 거리 누적 합은 1부터 K까지의 자연수 합을 구하는 것과 동일하다. 1+2+3+...+K는 $\frac{{(K*(K+1))}{2}$로 표현 가능하다.

 

③ 1부터 K까지의 합을 구하는 식을 이용해 start, end 범위를 조절할 수 있다.

 

$\frac{{(K*(K+1))}{2}$가 N보다 클 경우: 점프 거리 누적 합이 징검다리 개수보다 크다는 것은 어떻게 해도 N번째 징검다리를 밟을 수 없다는 뜻이 된다. 이런 경우에는 end = mid-1로 갱신해 더 작은 범위를 탐색할 수 있도록 한다.

 

$\frac{{(K*(K+1))}{2}$가 N보다 작을 경우:  이 때는 마지막 징검다리에서 긴 점프로 N번째 징검다리를 무조건 밟을 수 있게 된다. 문제에서 원하는 건 최댓값이기 때문에 N보다 값이 작은 범위에서 가장 큰 K를 찾기 위해 start = mid+1로 갱신한다.

 

3) 구현

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())

    answer = 0
    
    # 1+2+3+...+(K-2)+(K-1)+K=K(K+1)//2
    start, end = 1, N
    
    max_stone = float("-inf")
    
    while start <= end:
        mid = (start+end)//2
        
        jump_distance = (mid*(mid+1))//2
        
        # 점프 거리 누적합이 N보다 크면 N번째 징검다리를 못 밟음
        if jump_distance > N:
            end = mid-1
        else:
            max_stone = max(max_stone, mid)
            start = mid+1
        
    print(max_stone)

 

4) 어려웠던 점/배운 점

🚨 어려웠던 점

• 점프 거리 누적 합이 N보다 클 때, 작을 때의 의미를 파악하는 데에 시간이 조금 걸렸다.

❗ 배운 점

• 입출력 범위가 말도 안 되게 클 때는 $O(log_{N})$의 시간 복잡도를 갖는 이분 탐색 기법을 어떻게 적용할 수 있을지 고민해보자!