Baekjoon 1052번 물병

문제

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

걸린 시간

- 실패

시간초과 풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int n, k;
    cin >> n >> k;
    for(int i = 0; i <= pow(2, 24)-n; i++){
        int cnt = 0;
        int rn = n+i;
        for(int j = 24; j >= 0; j--){
            int tmp = pow(2, j);
            if(rn >= tmp){
                rn -= tmp;
                cnt++;
            }
        }
        if(cnt <= k){
            cout << i << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

물병을 2의 거듭제곱 중 큰 순서대로 줄여 나가면 줄여진 물병의 최소 개수를 구할 수 있다는 규칙을 찾아냈다. 하지만 pow 함수의 복잡도가 O(n) 임을 생각하지 못했고, 최악의 경우 2²⁴ * 24 * 23 / 2 = 4,630,511,616 번 반복되어 시간초과가 발생했다.

옳은 풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int n, k;
    cin >> n >> k;
    vector<int> p;
    for(int i = 24; i >= 0; i--) p.push_back(pow(2, i));
    for(int i = 0; i <= pow(2, 24)-n; i++){
        int cnt = 0;
        int rn = n+i;
        for(int j = 0; j <= 24; j++){
            int tmp = p[j];
            if(rn >= tmp){
                rn -= tmp;
                cnt++;
            }
        }
        if(cnt <= k){
            cout << i << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

0 부터 24 제곱까지의 계산이 중복되기 때문에 미리 구해놓은 후 사용하면, 줄일 수 있는 물병의 최소 개수를 상수 시간안에 구할 수 있어 2²⁴ * 24 = 402,653,184 로 통과할 수 있다.

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int n, k;
    cin >> n >> k;
    for(int i = 0; i <= pow(2, 24)-n; i++){
        int cnt = 0;
        int rn = n+i;
        while(rn > 0){
            if(rn%2 == 1) cnt++;
            rn /= 2;
        }
        if(cnt <= k){
            cout << i << "\n";
            return 0;
        }
    }
    cout << -1 << "\n";
    return 0;
}

다른 풀이로는 현재 값을 이분법으로 나누며 나머지가 1일 때, 즉 합쳐지지 못하는 물병의 개수가 발생할 때 마다 세어주는 방법이 있다.

검색을 해 보니 많은 사람들이 이 방법으로 문제를 해결했다. 하지만 개인적으론 처음 설명한 풀이 방법에 비해 직관적인 것 같지 않다.