99클럽 코테 스터디 2일차 TIL - 이분탐색 (백준 1072번 )

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

 

 

• 오늘의 학습 키워드 : 이분탐색
• 공부한 내용

import sys
import math

# 테스트 케이스의 수
T = int(sys.stdin.readline().strip())

for _ in range(T):
    N = int(sys.stdin.readline().strip())
    
    # 1. 최대 점프 횟수의 추정값을 구합니다.
    max_jump = math.isqrt(2 * N)  # math.isqrt()는 정수 제곱근을 구해줌

    # 2. 가장 큰 max_jump 값 중에서 조건을 만족하는 최대 값 찾기
    if max_jump * (max_jump + 1) // 2 <= N:
        print(max_jump)
    else:
        print(max_jump - 1

• 오늘의 회고
  • 일단 나는 항상 문제를 풀면,, 알고리즘보다 먼가 문제를 본지를 파악하려고 하는게 먼가 좀 문제가 있는것 같기두..
    일단 이 문제를 보고서 해석을 했다.
    N = 1 ~ N = (1 + 2 -1) 까지는 최대 징검다리 수 = 1
    N = (1 + 2 )~ N = (1 + 2 +3 -1 )까지는 최대 징검다리 수 = 2
    N = (1 + 2 +3 ) ~ N = (1 + 2 +3 + 4 -1 ) 까지는 최대 징검다리 수 = 3
    N = (1 + 2 +3 + 4  ) ~ N = (1 + 2 +3 + 4 + 5 -1 ) 까지는 최대 징검다리 수 = 4
    이 규칙은 이해 완료완료 했다,, 근데 그럼 이걸 어찌 풀건가? 그걸 생각해봤다
    
    
  • 그래서 생각한 풀이는 1 +. .. MAX =( 1+ MAX )MAX/2 = ( MAX +MAX^2 )/2  ~ MAX^2/2 이 맥스값을 찾아서.. 점점 내려가면 되지 않을까? 생각했다..
    

    

  • 이렇게 .. 복잡하게 생각했지만,, 이분탐색이라는 방법이 있었다는거 이 문제는 이분탐색이었다거~ 푸하하하하

이분탐색 공부한것도 써야하는데.. 아무래도 오늘은 시간이 별로 없어서 이정도만 쓰고 마무리 하겠다