[백준] 1052 - 물병(Java)

문제 파악

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

 

어려운 점

정답이 없는 경우 -1을 리턴해야 하는데 이 부분을 신경 쓰느라 규칙을 잡는 중요한 부분을 놓친 게 아닌가 싶다.

... 사실 -1이 나올 일이 없다 😅

풀이

주어진 수들을 2진수로 변환하여 풀도록 한다.

높이가 1인 컵을 한 개씩 추가할 때 기존 물컵들이 결합하여 변화하는 양상은 이진수의 연산과 닮아있다.

이진수로 변환하게 되면 각 자리수의 1은 차 있는 물컵을 나타낸다

 

예를 들어 높이가 1인 컵의 개수가 5일 경우에 대해 규칙을 알아보도록 하자

5 = 101(2) 즉 2개의 컵이 남는다.
(높이가 1인 컵 1개, 4인 컵 1개가 남는 형태)

현 상태에서 1인 물컵을 더하게 되면 6 = 110(2)로 바뀐다.
(높이가 1인 컵 두개가 결합하여 ➡️ 높이가 2인 컵 1개, 4인 컵 1개가 남는 형태)

코드

import java.io.*;

public class N1052 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] input = br.readLine().split(" ");
        int bottleCount = Integer.parseInt(input[0]);
        int filledBottleCount = Integer.parseInt(input[1]);
        int answer = 0;
        while (Integer.bitCount(bottleCount) > filledBottleCount) {
            bottleCount++;
            answer++;
        }
        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}