[BOJ C++] 백준 28245번: 배고파(Hard)

 📚 문제

[BOJ C++] 백준 28245번: 배고파(Hard)
https://www.acmicpc.net/problem/28245

 

---

 📝 입력 및 출력

 

---

 🔎 문제 풀이

• 먼저, x와 y를 조합하여 $2^x+2^y \geq 10^{18}$인 모든 수를 계산한다. $m$의 입력값 범위가 $1 \leq m \leq 10^{18}$이기 때문이다.
• $2^k \leq 10^{18},$ $k \times log{2}\leq 18,$ $k \leq 18/log2$(약 0.3) $=60$ 이므로 $y \leq 60$로 설정하여 계산한다.
• , pow() 함수나 비트 연산을 이용하면 2의 거듭제곱을 계산할 수 있다.
• 계산한 값과 그때의 x, y값을 모두 저장하고, 결과값으로 빠르게 검색하기 위해 map 자료형을 사용한다.
• 큰 범위의 수를 다뤄야하므로 int형이 아닌 long long 자료형을 사용해야한다.
  (참고: long long의 범위는 -9,223,372,036,854,775,808 (-2^63) ~ 9,223,372,036,854,775,807(2^63-1)이다.)
• 입력받은 값을 검색했을 때, 그 값이 map에 존재하는 경우 x, y값을 바로 출력한다. 그렇지 않은 경우에는 직전 값과 다음 값 중 더 가까운 값을 선택하여 결과를 출력한다.

---

 ⌨️ C++ 코드

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

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long n, m;
    cin >> n;
    map<long long, pair<int, int>> ma;
    for (int i = 0; i <= 60; i++) {
        for (int j = 0; j <= i; j++) {
            long long tmp = (1LL << i) + (1LL << j);  // 비트 연산으로 2의 제곱 수 만들기.
            ma[tmp] = pair<int, int>(j, i);
        }
    }

    map<long long, pair<int, int>>::iterator iter, lower, upper;
    for (int i = 0; i < n; i++) {
        cin >> m;
        if ((iter = ma.find(m)) != ma.end())  // 존재하는 경우.
            cout << iter->second.first << " " << iter->second.second << '\n';
        else {  // 존재하지 않는 경우 가장 가까운 값 찾기.
            lower = ma.upper_bound(m);
            if (lower != ma.begin()) {
                upper = lower--;  // iter2: m보다 큰 값, iter: m보다 작은 값

                if (abs(lower->first - m) <= abs(upper->first - m)) {  // m보다 작은 값이 더 가까운 경우.
                    cout << lower->second.first << " " << lower->second.second << '\n';
                } else {  // m보다 큰 값이 더 가까운 경우.
                    cout << upper->second.first << " " << upper->second.second << '\n';
                }
            } else
                cout << 0 << " " << 0 << '\n';
        }
    }
}