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

 

 

문제

백준 11561번  | 실버 3

#이분탐색 #수학

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

 

풀이 & 코드

처음에는 문제 이해가 안가서, 징검다리가 1개 있는 경우부터 ~ 13개 있는 경우까지 직접 계산해봤다.

예를 들어, 징검다리가 13개인 경우는 1번, 4번, 8번, 13번을 건너 총 4개의 징검다리를 건너고 이의 거리는 1 3 4 5가 된다.

 

* 문제에서 N은 10^16이라 주어졌기에, 일반적인 int로 풀면 타임아웃이 발생할 것 같아, long으로 표현했다.

* 두 번째 점프부터 이전 점프 + 1 ~  를 점프한다는 점에서 등차수열을 떠올림

* 등차수열의 합 공식 = (n * (n+1)) / 2

* 결국, 마지막 N번째 징검다리 이전에 최대한 많은 징검다리를 건너야 하므로, N 이전까지의 숫자들 사이의 등차수열을 구하면 된다.

public class q11561_징검다리건너기 {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        while(t-- > 0){
            long n = Long.parseLong(br.readLine());
            long start = 1;
            long end = 1000000000;

            long answer = 0;
            while(start <= end){
                long middle = (start + end) / 2;
                if(middle * (middle+1) / 2 <= n) {
                    answer = middle;
                    start = middle + 1;
                } else {
                    end = middle - 1;
                }
            }
            System.out.println(answer);
        }
    }
}

 

 

회고 & 배운점

* 이분탐색 공부 (https://www.notion.so/dev-if/12430ed61f7880e4bff9c318f2e6f7c4)

* 선형탐색과 이분탐색의 속도 차이 

   * 선형탐색 : O(n) 

   * 이분탐색 : O(log n) → 리스트가 정렬되어 있으며, 검색 범위를 반으로 줄임