[BaekJoon] 27436번 - 벌집 2 [Java][C++]

문제 링크

---

1. 문제 풀이

BaekJoon 2292번 - 벌집 문제에서 시간 제한이 더 타이트하고 $N$ 의 범위가 커진 문제로 이전처럼 1씩 증가시켜보며 해결할 수 없다. 여기선 보다 효율적인 탐색인 이분 탐색과 매개 변수 탐색을 활용하면 해결할 수 있다.

매개 변수 탐색은 주어진 $N$ 의 범위에서 가능한 정답의 하한과 상한을 정하고 조건을 만족하는지 비교하며 찾으면 된다. 방은 최소 $1$ 개는 지나야 하기에 하한은 $1$ 이며, $N$ 이 최대 $9 \times 10^{18}$ 이므로 $9 \times 10^{18} = 3 \times n \times (n - 1) + 1$ 을 활용하면 대략 $2,000,000,000$ 정도로 어림할 수 있다. 정답이 $1$ ~ $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);
}

---