백준 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이 주어졌을 때 강을 건너면서 밟게되는 징검다리 갯수의 최대값을 구하려면 징검다리를 건너뛰는 거리를 1부터 시작해서 이전 보다 점프한 거리를 1씩만 늘려가며 강을 건너야 한다.

즉, 1부터 특정값 k 까지의 합을 구했을 때 이 값이 징검다리의 갯수 N보다 작거나 같은 값 중에 가장 큰 값이 될 때가 곧 징검다리를 밟는 갯수가 최대화 되는 경우이다.

이 때, 1부터 특정값 k 까지의 합은 말 그대로 강을 건널때 뛰었던 거리의 총합을 뜻하는 것이지 밟았던 징검다리의 갯수를 뜻하는 것이 아님을 유념한다.

여기서 밟았던 징검다리의 갯수는 1부터 특정값 k 까지의 합을 구할 때 특정값 k에 해당된다.

(건너뛴 거리 1 -> 첫번째 징검다리, 건너뛴 거리 2 -> 두번째 징검다리, ... 건너뛴 거리 k -> k번째 징검다리)

 

1부터 특정값 k 까지의 합이 징검다리의 갯수 N보다 작거나 같은 경우를 식으로 풀어쓰자면 다음과 같아진다.

N >= k * (k + 1) / 2

이를 다시 한번 풀어써보면 다음과 같은 이차방정식이 만들어진다.

0 >= k^2 + k - 2N

여기서 이차방정식의 근의 공식을 활용하여 k의 값을 구하고자 한다면 다음과 같이 코드를 작성해주어야 한다.

((long)Math.sqrt(1 - (4 * n * -2)) + 1) / 2;

sqrt 함수 수행 이후에 +1을 해준 이유는 다음과 같다.

근의 공식에서 분자는 -b (+-) Math.sqrt(b^2 - 4 * a * c) 처럼 이루어져 있다. 이때 a는 첫번째 항, b는 두번째 항, c는 세번째 항이다.

우리는 강을 건널 때 밟게되는 징검다리의 갯수를 최대화 해야 하므로 여기서 구할 수 있는 근의 값을 최대화 해야 한다.

근의 공식에서 얻을 수 있는 값을 최대화 할 때 분모는 2밖에 존재하지 않기 때문에 건드릴 수 있는 부분이 없으나, 분자의 경우 (+-) 와 같이 두 가지의 근이 나올 여지가 존재한다. 이를 이용해 얻을 수 있는 근의 크기를 최대화 해보자.

우선 -b (+-) 를 Math.sqrt() 함수 뒤로 넘겨보면 Math.sqrt(b^2 - 4 * a * c) (+-) -b 가 된다.

(+-) 에서 - 를 선택해주면 Math.sqrt(b^2 - 4 * a * c) - (-b) 가 되는데, 여기서 - (-b) 는 +b로 변환이 가능하다.

이에 따라 식은 다음과 같아진다.

Math.sqrt(b^2 - 4 * a * c) + b

여기서 b는 이차방정식의 두번째 항에 해당하는데, 두번째 항의 계수는 1이므로 +1이 되는 것이다.

이제 첫번째 항을 뜻하는 a에 첫번째 항의 계수 1, 세번째 항을 뜻하는 c에 세번째 항의 계수 n * -2 를 넣어주면 다음과 같은 식이 완성된다.

((long)Math.sqrt(1 - (4 * n * -2)) + 1) / 2;

 

물론 이를 통해 얻은 값이 반드시 밟게되는 징검다리의 최대값이라고는 할 수 없으므로 이분탐색을 수행해서 정밀한 값을 얻어내어 문제를 해결했다.

1. start 를 0 으로 초기화 하고, end 를 ((long)Math.sqrt(1 - (4 * n * -2)) + 1) / 2 로 초기화해준다.

2. start <= end 조건을 만족하는 동안 아래와 같은 로직을 반복 수행해준다.

  - mid 를 (start + end) / 2 로 초기화 하고 sum 을 (mid * (mid + 1)) / 2 로 초기화 해준다. 이때 mid 는 이번 반복에서 징검다리를 밟은 횟수에 해당되는 값이다.

  - sum 이 징검다리의 갯수 n보다 작거나 같다면 현재 mid 값과 result 값 중 더 큰값을 result 에 저장해주고 start 를 mid + 1 로 초기화 하여 mid 값이 더 커지는 방향으로 범위를 줄여준다.

  - sum 이 징검다리의 갯수 n보다 크다면 end 를 mid - 1 로 초기화하여 mid 값이 더 작아지는 방향으로 범위를 줄여준다.

3. 반복문이 끝나고 나면 result 값을 출력시켜준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        new Main().solution();
    }

    private void solution() throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int i = 0; i < tc; i++) {
            long n = Long.parseLong(br.readLine());
            long start = 0L;
            long end = ((long) Math.sqrt(1 - (4 * n * -2)) + 1) / 2; // 이차방정식 근의 공식

            long result = 0;
            while (start <= end) {
                long mid = (start + end) / 2;

                long sum = (mid * (mid + 1)) / 2;
                if (sum <= n) {
                    result = Math.max(mid, result);
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }
            bw.write(result + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

 

1부터 특정값 k 까지의 합이 징검다리의 갯수보다 작거나 같은 값 중에 가장 큰 값을 구하는데 있어 이차방정식을 만들고 이 방정식의 근의 공식을 이용해 밟을 수 있는 징검다리 갯수의 최대 크기를 설정해 이분탐색의 end 값으로 활용한다는 아이디어를 떠올리는 과정이 굉장히 힘겨웠던 문제

결국 특정값 mid 를 마지막으로 하여 건너뛴 거리의 총합과 징검다리의 갯수 n을 비교하여 조건에 따라 범위를 줄여주는 식으로 정답을 찾았으므로 이분탐색 문제에 해당된다.