백준 문제 풀이(1052번) java

문제

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

풀이

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이 문제는 10진수를 2진수로 바꿔서 푸는 문제이다. 문제의 예제 입력을 보면 물병의 개수가 3개일 때 이를 1개로 줄일 수 있는 방법은 없다. 그 이유는 3을 2진수로 나타내면 11(2)이므로 이를 1개로는 줄일 방법은 없다. 그래서 물병 1개를 구매하여 총 4개를 2진수로 바꿔 100(2)으로 문제를 해결해야 한다. 2진수로 풀어야하는 이유는 위의 문제 조건 때문이다. 2진수는 나누어떨어지면 0 떨어지지 않으면 1로 나타낸다. N개의 물병을 K개가 넘지 않는 물병으로 옮기기 위해서는 N을 2진수로 나타냈을 떄 1의 개수가 K개보다 작거나 같아야한다. 같으면 딱 K개로 N개의 물병을 나눌 수 있는 것이고, 작으면 N개의 물병을 나눌 떄 K개보다 적게 필요하다는 것이다. 문제의 조건을 보면 K개를 넘지 않는 물병을 만들라고 했으므로 N개의 물병을 나눴을 때 K보다 크지만 않으면 된다.

코드

package Category;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class q_1052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int count;
        if (N <= K) { // 처음 들어온 N과 K값을 비교했을 때 K가 N보다 크다면 N개의 물병은 무조건 K개로 나눌 수 있다.
            System.out.println(0); // 위의 조건이 성립하면 구매할 물병이 없음
            return;
        }
        int buy = 0;
        while (true) {
            count = 0;
            int num = N;
            while (num != 0) {
                if (num % 2 == 1) { // 2진수로 나타낼 때 나머지가 나올 때 마다 count값을 1씩 늘려준다.
                    count += 1;
                }
                num /= 2;
            }
            if (count <= K){ // 2진수로 나타냈을 때의 1의 개수가 K보다 작거나 같으면 while문을 종료하고 buy로 구매할 물병의 개수를 출력한다.
                break;
            } //count가 K보다 크다면 이는 N개를 K개로 만들 수 없다는 것이므로 N과 buy(구매할 물병의 개수)를 증가시켜 다시 while문을 돌게한다.
            N += 1;  
            buy += 1;

        }
        System.out.println(buy);

    }
}