물병

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

풀이

문제를 읽어보면 간단한 규칙 하나를 알 수 있다.

2의 제곱인 n은 하나의 물병으로 합칠 수 있다.

이를 통해 n을 2로 나누었을 때 나머지가 1이면 들고가야하는 물병이 1개 더 생긴다. (합친 물병 + 나머지)

만약 cnt 값이 k보다 작다면 반복문을 멈추고 r이 상점에서 산 물병의 개수이기에 r을 정답으로 출력한다.

만약 cnt가 k보다 크다면 다시 2로 나누는 과정을 반복한다. 이 때 새로운 물병을 상점에서 샀기 때문에 r,n을 증가시켜 줘야한다.

만약 처음부터 n이 k보다 작거나 같다면 바로 0을 출력하고 끝낸다.

코드

import java.io.*;

public class Main {
    static int n, m, k;


    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[] line = br.readLine().split(" ");
        n = Integer.parseInt(line[0]);
        k = Integer.parseInt(line[1]);

        int ans = 0;
        if (n <= k)
            ans = 0;

        else {
            int r = 0;
            while (true) {
                int cnt = 0;
                int num = n;
                while (num != 0) {
                    if (num % 2 == 1)
                        cnt++;
                    num = num / 2;
                }

                if(cnt <= k) {
                    break;
                }
                r++;
                n++;
            }
            ans = r;
        }
        bw.write( ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}