[99클럽 코테 스터디 TIL#2일차] 백준 11561

문제

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

 

 

문제 풀기

1. 이분 탐색

2번째로 도전하는 이분 탐색 문제이다. 밟는 징검다리 수의 최대 값을 찾으라고 한다. 근데 제한사항이 택도 없이 큰 숫자라 완전 탐색은 안 된다. 이분 탐색을 사용해야겠다고 생각했다.

 

2. 등차 수열

"두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다." 라는 것에서 등차 수열을 사용하면 좋겠다는 생각이 들었다.

 

 

작성한 코드

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long test = sc.nextLong();
        
        for(int i = 0; i < test; i++) {
            long n = sc.nextLong();
            
            long result = 0;
            long left = 0;
            long right = (long) Math.sqrt(2*n);
            
            while(left <= right) {
                long mid = (left + right) / 2;
                long sum = mid * (mid + 1) / 2;
                
                if(sum <= n) {
                    result = Math.max(result,mid);
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            System.out.println(result);
        }
    }
}