[파이썬] 11561번: 징검다리 / 이분탐색

---

 

1. 백준 11561번 징검다리

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

 

N번 징검다리는 반드시 밟아야 한다. 

:: 마지막 징검다리는 밟아야 한다는 뜻이다.

:: 예를 들어, 입력이 100이면 13번째 징검다리는 꼭 건너야 한다는 뜻이다. 100을 밟는다는 뜻 아님!

 

2. 오늘의 회고

* 정답은 아래에 있습니다.

첫 번째 접근: 단순 구현으로 풀기 :: 시간초과

단순 구현을 통해서 풀어보았다. 제시문을 통해 징검다리가 1 2 3 4 5 6 7 8 9 10 ... 중 1 3 6 10 에 해당한다는 것을 파악하고 단순 반복문을 통해 N에서 빼는 값을 늘리는 방식으로 해결하였다.

 

N의 범위는 (1 ≤ N ≤ 10**16) 이기 때문에 시간초과 발생한다.

T = int(input())

for j in range(T):
    n = int(input())
    i = 2
    cnt = 1
    if n==1 or n==2:
        print(1)
    else:
        while True:
            n = n-i
            i = i+1
            cnt = cnt+1
            if n<0:
                cnt = cnt-1
                print(cnt)
                break
            elif n==0:
                print(cnt)
                break

 

두 번째 접근: 이분탐색 ::성공

1. 입력 범위 파악하기

징검다리의 총 수 N의 범위가 (1 ≤ N ≤ 10**16)로 주어졌기 때문에 이분탐색임을 파악할 수 있다. 또한, 문제에 접근할 때 어떤 것을 더하거나 빼어서 최대 최소를 구하는 문제는 이분탐색을 고려해보아야 한다.

 

2. 풀이과정

1) Left, Right 정하기

징검다리 점프를 1번 하면 거리는 1, 점프를 두 번 하면 거리는 1+2, 점프를 세 번 하면 거리는 1+2+3으로 등차수열대로 거리가 늘어난다. 따라서 점프는 K번하면 거리는 K*(K+1) // 2 만큼 늘어나게 된다. 

 

징검다리를 100개 주어진다고 친다.

 

점프를 12번 하면 징검다리 개수(거리)는 12*(12+1) // 2 = 78개가 된다

   ====> 주어진 100개보다 한참작음 (최대에 부합하지 않음)

점프를 13번 하면 징검다리 개수(거리)는 13*(13+1) // 2 = 91개가 된다. 

   ====> 주어진 100개보다 9개 작음 (최대에 부합함)

점프를 14번 하면 징검다리 개수(거리)는 14*(14+1) // 2 = 105개가 된다.

   ====> 주어진 100개보다 많음 (징검다리 개수보다 많아 성립하지 않음 )

 

따라서 징검다리 개수는 13개이다.

점프 횟수가 늘어나면 갈 수 있는 징검다리(거리)가 많아진다. 단, 주어진 N보다 작거나 같아야 한다.

 

Left와 Right는 점프 횟수를 나타내고 Mid부터 시작한다.

Left = 0 Right = 10**16

Mid = (Left + Right) // 2

거리 = (Mid * (Mid +1)) // 2

 

 

2) 이분탐색

 

만약 거리가 주어진 N보다 작으면 일단 값 저장 cnt = mid 거리가 최댓값인지 확인해야 하기 때문에 Left = mid + 1 

만약 거리가 주어진 N보다 크면 거리의 크기를 줄여야 하기 때문에 Right = mid - 1

 

 

T = int(input())

for j in range(T):
    n = int(input())
    cnt = 0
    left = 1
    right = 10 ** 16
    while left <= right:
        mid = (left +right)//2
        ds = (mid*(mid+1))//2
        if ds < n:
            cnt = mid
            left = mid +1
        elif ds > n:
            right = mid -1
        else:
            cnt = mid
            break

    print(cnt)