[BaekJoon] 1052 물병

1.  문제 링크

2.  문제

요약

• 각 물병에는 1L의 물이 들어있고 지민이는 N개의 물병을 가지고 있습니다.
• 각 물병에는 물을 무한대로 부을 수 있습니다.
• N개의 물병에 있는 물을 합쳐서 비어있지 않은 물병의 개수가 K개를 넘지 않도록 합니다.
• 물을 합칠 때는 같은 양의 물이 들어있는 두 물병을 하나의 물병으로 합칩니다.
• 위 방법을 이용하여 비어있지 않은 물병을 K개 이하로 만들 때에 사야하는 1L 물이 들어있는 물병의 최솟값이 몇 개인지 구하는 문제입니다.
• 입력: 첫 번째 줄에 N과 K가 주어집니다.
• 출력: 사야하는 물병의 최솟값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main {
	public int getBottleNum(int n, int k) {
		int bottleNum = 0;
		while(true) {
			int temp = n + bottleNum;
			int count = 0;
			while(temp > 0) {
				if(temp % 2 == 1) {
					count++;
				}
				temp /= 2;
			}
			if(count <= k) {
				break;
			}
			bottleNum++;
		}
		return bottleNum;
	}
	
	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();
		StringTokenizer st = new StringTokenizer(input);
		int n = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());
		br.close();
		Main m = new Main();
		bw.write(m.getBottleNum(n, k) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 위 문제는 아래의 순서로 풀어갑니다.

1. 입력받은 N을 하나의 물병으로 합쳐갑니다. 같은 양이 남은 물병들만 합치기 때문에 2로 나누어가며 하나의 물병으로 합칩니다.
2. 만약 위 과정에서 나머지가 생긴다면 count의 값에 1을 더합니다. 여기서 count는 비어있지 않은 물통의 개수를 뜻합니다.
3. 위 과정을 통해 하나의 물병으로 합친 후 비어있지 않은 물통의 개수 count가 입력받은 K보다 작거나 같다면 조건을 만족하기 때문에 위 과정의 반복을 끝냅니다.
4. 만약 count가 K보다 크다면 조건을 만족할 때까지 반복하고 각 반복마다 1L의 물병을 하나씩 사서 N의 값을 1씩 늘려나갑니다.