[BOJ-11561] 징검다리

백준 11561 징검다리

 

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

11561번: 징검다리

 

문제 설명

 

 - 승택이는 강을 건너려 한다.

 

 - 강엔 1번부터 시작해 2번, 3번, ..., N번 징검다리가 있다.

 

 - 승택이는 제자리뛰기 실력을 발휘해 적절한 개수의 징검다리만 밝고 가기로 했다.

 

 - 징검다리를 건너는 규칙은 다음과 같다.

   1. 첫 징검다리는 점프해서 아무 것이나 밟을 수 있다. 이 점프가 첫 점프이다. 
   2. 두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다.
   3. N번 징검다리는 반드시 밟아야 한다.
   4. N번 징검다리를 밟은 후 강 건너로 이동할 땐 점프를 하지 않으므로 위의 규칙이 적용되지 않는다.

 

 - 규칙을 지키며 강을 건널 때, 밟을 수 있는 징검다리의 최대 수는 몇 개일까?

 

 

---

 

입력 값

 

 - 첫째 줄에 테스트 케이스의 수 T가 주어진다.

 

 - 각 테스트 케이스는 정수 한 개로 이루어져 있으며, 징검다리의 총 수 N을 의미한다.

   ( 1 <= N <= $10^(16)$ )

 

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 징검다리를 건널 수 있는 방법은 N번째 징검다리에 도착하는 방법의 수와 같다.

 

 - 즉, 최대의 징검다리를 건너서 N번째 징검다리에 도착하면 되는 것이다.

 

 - 가장 많은 징검다리를 건너는 방법은 1번부터 차례대로 건너는 것이다.

 

 - 즉, 1~K까지 순서대로 건넜을 때 N보다 작거나 같으면 K번 건너서 도착한 것이다.

 

 - 하지만, K가 가능한 모든 값을 살펴보기에는 너무 많은 경우의 수가 존재한다.

 

 - 이때 사용하는 것이 파라메트릭 서치이다.

파라메트릭 서치(Parametric Search)

 

 - 밟은 징검다리의 개수를 살펴보면 특징이 존재한다.

 

 - 최대 K번까지 밟을 수 있다고 가정하자, 그렇다면, 1~K-1번으로도 도착이 가능하다는 것이다.

   왜냐하면, K번째에 N으로 도착한다면, K-1번째에 K-1+K를 한 번에 뛰면 똑같이 N에 도착하기 떄문이다.

 

 - 즉, 밟은 수 K가 주어지고, 그때 도착이 가능할 때 T, 불가능할 때 F 를 리턴한다고 하면,

   1~K는 T이고, K+1~N까지는 F가 된다.

 

 - 그러므로 파라메트릭 서치를 사용할 수 있다.

 

 - 결론적으로, 밟을 수 있는 최대의 개수까지 이분탐색을 하면서

   해당 수를 밟으면서 도착할 수 있는지 판단하면 된다.

 

---

 

 

소스 코드

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(bf.readLine());

        for(int i=0;i<T;i++){
            long N = Long.parseLong(bf.readLine());
            long start=0;
            long last= (long) Math.sqrt((2*N-1));
            long result=0;
            while(start<=last){
                long mid=(start+last)/2;
                long sum=  (mid) *(mid+1)/2;
                if(sum<=N){
                    result=Math.max(mid,result);
                    start=mid+1;
                }
                else{
                    last=mid-1;
                }
            }
            System.out.println(result);


        }

    }

}