2022.02.12 49일차

백준 1052번 (물병)

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

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

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

나의 풀이

1. 물병 N, 한 번에 옮길 수 있는 물병 K, 조건: 구매하는 물병은 최소한으로 하도록 접근
2. N2를 2로 나누었을 때 나머지가 발생하면 카운트 증가, 0이 될때까지 반복
3. 카운트와 K값 비교, 카운트가 더 크면 물병을 구매
4. 카운트가 더 크면 물병을 구매, N 1을 증가시키고 다시 반복
5. 카운트가 작거나 같으면 구매한 물병 개수 출력

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 answer = 0;
        while (true) {
            int count = 0;
            int N2 = N;
            while (N2 != 0) {
                if (N2 % 2 == 1) {
                    count += 1;
                }
                N2 /= 2;
            }
            if (count <= K)
                break;
            N += 1;
            answer += 1;
        }

        System.out.println(answer);
    }
}

생각하기

• 이진수로 접근 가능, 1의 개수가 물병의 개수
  Integer.bitCount