[Java] 백준 1025 : 물병

🔗 문제 내용

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

1052번: 물병

🌱 문제 풀이 방법

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 가 이 문제의 포인트다.

같은 양의 물을 고르기 위해 N개의 물병을 두개로 나눈다.

만약, 이때 2로 안 나눠지다면 물병을 합칠 수 없기 때문에 옮겨야 하는 물병의 개수를 늘린다.

옮겨야 하는 물병이 옮길 수 있는 물병의 개수 K를 넘기면 한번에 옮길 수 없기 때문에 물병을 1개 추가 구매한다.

🤔 공부가 필요한 부분

문제를 이해하는데 시간이 매우 오래 걸렸다... 

유연하게 생각하는 훈련이 많이 필요한 것 같다.

문제 푸는걸 도와준 익명의 고라니와 코치님께 감사 인사를 전한다.

+ 2진수로 푸는 방법도 있는데 고민해봐야겠다.

💻 코드

import java.util.*;
import java.io.*;
import java.lang.*;
public class Main {
    static int N,K,cnt;
    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        cnt = 0;
        int temp = N;
        boolean flag = true;
        while(flag){
            if(isBuy(N)) flag = false;
            else N+=1;
        }
        if(N-temp>=0){
            System.out.println(N-temp);}
        else System.out.println("-1");
    }

    static boolean isBuy(int n){
        int temp=0;
        while(n>0){
            if(n%2==1){
                n/=2;
                temp++;
            }else n/=2;
        }
        if(temp<=K){
            return true;
        }else return false;

    }
}