백준 11561 - 징검다리( Python )

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

11561번: 징검다리

이진탐색 실버 3 레벨의 문제

 

등차수열로 풀어야한다는 것을 생각하지 못해서 다른 분의 풀이를 참고하여 풀게되었다.

- 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야한다

    -> 3, 4, 5, 6 과 같은 규칙이 있을 것으로 생각해야됨 3, 5, 9, 15 와 같은 불규칙적인 점프는 도출해낼 수 없음

- 최대의 징검다리 수

     -> 점프마다 최소 거리를 뛰어야하므로 1이라 가정하고 규칙을 구할 수 있음

 

=> 즉, 최소 거리를 뛰는 규칙을 찾아야하기 때문에 

등차수열을 생각 할 수 있다. 공차를 구하는 것이 핵심

 

공차를 이분탐색의 mid값으로 두고 문제를 구하면 된다.

t = int(input())

for _ in range(t):
  n = int(input())
  start = 1
  end = n
  result = 0

  while start <= end:
      mid = (start + end) // 2
      if ((mid+1) * mid ) // 2 <= n: # 건널 수가 징검다리 개수보다 작으면
        start = mid + 1
        result = mid
      else: # 징검다리 개수보다 큰경우
        end  = mid - 1
  print(result)