백준 1052: 물병 [C/C++]

https://www.acmicpc.net/problem/1052

1052번: 물병

코드

 

 

#include <vector>
#include <algorithm>
using namespace std;
int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int N, K;
    cin >> N >> K; K--;
    vector<int> arr = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216};
    while (K--) N -= *(lower_bound(arr.begin(), arr.end(), N) - 1);
    cout << *lower_bound(arr.begin(), arr.end(), N) - N;
    return 0;
}
 

---

풀이

물의 양이 2^N 리터 밖에 될 수 없다는 것을 알아야 풀 수 있는 문제 입니다.

그 이후로는 이분탐색으로 쉽게 풀 수 있습니다.