[백준,c++] 1052번 - 물병

문제

1052번: 물병

 

코드

#include <iostream>
using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int N,K; cin>>N>>K;
    
    int ans = 0;
    
    for(ans;; ans++){
        int cnt = 0;
        int temp_N = N;
        while(temp_N!=0){
            if(temp_N%2) cnt++;
            temp_N/=2;
        }
        if(cnt<=K) break;
        N++;
    }
    
    cout<<ans;
}

 

풀이

아래의 입출력으로 한번 설명해 보겠습니다.

13개의 물병을 합치게 되면 결국 최종적으로 3개의 물병이 남게 됩니다. 나누는 과정은 아래 이미지와 같고, 코드상으로는 while(temp_N!=0) 부분입니다.

현재 남은 물병 3개는 한 번에 가져갈 수 있는 물병 개수 K보다 크기 때문에 물병을 또 추가하여 남은 물병 수를 줄여야 합니다.

물병을 추가하는 과정은 N++입니다. 이제 다시 위 작업을 반복하여 "남은 물병 개수 <=K" 가 될 때까지 계산하여 최종적으로 N을 추가해준 횟수를 출력하면 정답이 됩니다.

문제에서 만약 정답이 없을 경우에는 -1을 출력하라고 했는데 정답이 없는 경우는 없으니 따로 처리해 주지 않아도 됩니다.