[백준] 27436번 - 벌집 2 [Java][C++]

문제 링크

---

1. 문제 풀이

각 방마다 규칙적인 숫자가 부여되어 있는데 특정 방까지 최소 개수의 방을 지나서 갈 때, 몇 개의 방을 지나가면 도착할 수 있는지 구하는 문제다. $1$ 개의 방을 지나면 갈 수 있는 방은 1번 방 하나뿐이며, $2$ 개의 방을 지나면 갈 수 있는 방은 2 ~ 7번 방, $3$ 개의 방을 지나면 갈 수 있는 방은 8 ~ 19번 방, … 이렇게 구성된다.

잘 보면 규칙을 확인할 수 있는데 거리 1에서는 $1 \sim 1$, 거리 2에서는 $2 \sim 7$, 거리 3에서는 $8 \sim 19$, 거리 4에서는 $20 \sim 37$ 이런식으로 거리 $n$ 에서는 $6 \times (n - 1)$ 개의 방이 존재한다. 이는 등차 수열을 이루므로 등차 수열의 합 공식에 따라 거리 $n$ 에서는 최대 $3 \times n \times (n - 1) + 1$ 번 방까지 갈 수 있다.

위 공식을 통해 $n$ 을 $1$ 부터 증가시켜보며 찾으면 간단하게 찾을 수 있지만 이 문제는 시간 제한과 $N$ 의 범위 때문에 단순한 탐색으로는 찾을 수 없다. 여기선 보다 효율적인 탐색인 이분 탐색과 매개 변수 탐색을 활용하면 해결할 수 있다.

매개 변수 탐색은 주어진 $N$ 의 범위에서 가능한 정답의 하한과 상한을 정하고 조건을 만족하는지 비교하며 찾으면 된다. 방은 최소 $1$ 개는 지나야 하기에 하한은 $1$ 이며, $N$ 이 최대 $9 \times 10^{18}$ 이므로 $9 \times 10^{18} = 3 \times n \times (n - 1) + 1$ 을 활용하면 대략 $2,000,000,000$ 정도로 어림할 수 있다. 정답이 $1 \sim 2,000,000,000$ 사이에 반드시 존재하므로 이분 탐색을 통해 $N$ 의 값을 찾아나가면 된다. 이때 $N$ 을 포함하는 거리를 구해야하므로 Lower bound로 탐색했다.

---

2. 코드

1. 이분 탐색 + 매개 변수 탐색 [Java]

import java.io.*;

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

        long N = Long.parseLong(br.readLine());

        System.out.println(lowerBound(N));
    }

    static long lowerBound(long key) {
        long left = 1;
        long right = 2_000_000_000;

        while (left < right) {
            long mid = (left + right) / 2;

            if ((3 * mid * (mid - 1) + 1) < key) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }
}

2. 이분 탐색 + 매개 변수 탐색 [C++]

#include <bits/stdc++.h>
using namespace std;

long long lower_bound_param(long long key) {
    long long left = 1;
    long long right = 2000000000;

    while (left < right) {
        long long mid = (left + right) / 2;

        if ((3 * mid * (mid - 1) + 1) < key) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return right;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n;
    cout << lower_bound_param(n);
}

---

3. 풀이 정보

1. 이분 탐색 + 매개 변수 탐색 [Java]

언어	시간	메모리	코드 길이
Java 11	112 ms	14248 KB	647 B

2. 이분 탐색 + 매개 변수 탐색 [C++]

언어	시간	메모리	코드 길이
C++ 17	0 ms	2020 KB	514 B

---