백준 1052번 : 물병 (Java)

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

1052번: 물병

---

[풀이]

• 다수의 블로그에서 비트마스킹 유형의 문제라고 알려주지만, 저는 비트마스킹이 아닌 반복문을 이용해서 풀었습니다.
• 먼저, N이 K보다 작을 경우에는 더 구매할 필요가 없기 때문에 0을 반환합니다.
• N이 2일때부터 하나씩 나열을 해보겠습니다.
  • 여기서, 물병을 합칠 때 문제에서 합치는 방식을 최대한 한다고 가정하겠습니다.
• 이렇게 진행할 경우, N이 2진수일 때 1이 되는 것을 확인 할 수 있습니다.
• 즉, 주어진 조건내에서 -1을 반환할 일은 없다는 것을 알 수 있습니다.
• 더불어, N을 2로 나누면서 물병이 남을 경우 count 변수에 1을 더하며 K보다 작은지 확인하는 식으로 진행했습니다.
• 만약, count 변수가 K보다 작다면, 해당하는 buy 변수를 출력합니다. (K보다 클경우, N을 copyN 변수에 다시 집어넣어 이전 과정을 반복합니다.)

---

[코드]

 

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

public class Main {
    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 = 0;
        if (N <= K) {
            System.out.println(0);
            return;
        }
        int buy = 0;
        while (true) {
            count = 0;
            int copyN = N;
            while (copyN != 0) {
                if (copyN % 2 == 1) {
                    count += 1;
                }
                copyN /= 2;
            }
            if (count <= K)
                break;
            N += 1;
            buy += 1;
        }
        System.out.println(buy);
    }
}