백준(C, C++)/실버

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

치킨먹고싶어요 2022. 7. 11. 17:51

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

 

1052번: 물병

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번

www.acmicpc.net

코드

 

 

Z#include <iostream>
#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 리터 밖에 될 수 없다는 것을 알아야 풀 수 있는 문제 입니다.

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