[백준] 11561번 : 징검다리 - JAVA

 

 

11561 징검다리

 

 

 

이번 문제의 핵심은 이전에 점프한 거리보다 1이상 더 긴 거리를 뛴다는 것과 밟을 수 있는 징검다리의 최대 개수를 구하라는 것이다. 

문제 내용에 2번째 규칙은 "두 번째 점프부터는 이전에 점프한 거리보다 1 이상 더 긴 거리를 뛰어야만 한다"이고 이 문장을 통해 등차수열인 것을 알 수 있으므로 등차수열의 합 공식을 사용하면 된다.

 

등차수열 합 공식

$ \frac{n(n + 1)}{2} $

밟을 수 있는 징검다리의 최대 개수를 구하는 문제이기 때문에 등차수열의 합이 입력 n보다 작거나 같은 수 중에 최댓값을 찾으면 된다. 예를 들어 징검다리가 10개인 경우 1, 2, 3, 4번 징검다리를 건너가면 해결된다.

 

입력의 범위가 $10^{16}$이기 때문에 자료형은 int가 아닌 long으로 선언하였고 반복문으로 수를 증가시키며 값을 찾으면 시간 초과가 발생하기에 이분탐색을 사용하여 문제를 해결하였다.

자료형 long 범위: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
   자료형 int 범위: -2,147,483,648 ~ 2,147,483,647

 

 

(2024-06-12 추가) 

사람들이 얼마 방문하지 않은 현재 필자의 블로그에 해당 포스팅이  조회수가 늘고 있어 내용을 추가한다(뿌듯하다).

아래 소스에서 right 변수의 초기값을 10억으로 설정한 이유는 더 큰 값으로 설정할 경우 등차수열 합 공식을 적용할 때(sum 변수) 곱셈에서 long 자료형의 범위를 초과할 수 있으며 등차수열의 합(sum)이 $10^{16}$ (최대 입력 n)보다 작기 때문에 right 변수의 초기값을 10억으로 설정한 것이다.

 

 

성공 소스

public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            long n = Long.parseLong(br.readLine());
            long left = 0;
            long right = 1_000_000_000L;
            // long right = Integer.MAX_VALUE; 이것도 문제 없다.
            long result = 0;

            while (left <= right) {
                long mid = (left + right) >>> 1;
                long sum = (mid * (mid + 1)) / 2; // 등차수열 합 공식 적용

                /*
                문제 규칙 기준에서 입력 n에 대한 등차수열의 합은 n보다 작을 수밖에 없다.
                등차수열의 합이 n보다 작을 때를 찾아 해당 값(mid)과 이전 결과값(result) 중 최댓값 출력한다.
                 */
                if (sum <= n) {
                    // 이전 결과값과 현재 결과값 중 더 큰 값을 세팅한다.
                    result = Math.max(mid, result);
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }

            sb.append(result).append("\n");
        }

        System.out.println(sb);

        br.close();
    }

}