[백준 1052번] 물병 - JAVA

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

1052번: 물병

<풀이>

사용한 알고리즘 : 비트마스킹

 

풀이 전략

: 입력한 숫자를 2진수로 생각하고, 해당 2진수 안에 있는 1의 개수가 K개 이하가 될 때까지 1씩 더한다.

  (비트 1의 개수가 곧 물병의 개수를 의미하기 때문이다.)

   ex ) 000000001   = 1L 물병 1개  => 총 물병의 개수 : 1

          000000010   = 2L 물병 1개   => 총 물병의 개수 : 1

          000001010   = 8L 물병 1개, 2L 물병 1개  => 총 물병의 개수 : 2

 

따라서 만약 N=13으로 주어졌을 경우, 이를 2진수로 치환하면

13 = 00001101(2) = 8L 물병 1개, 4L 물병 1개, 1L 물병 1개   => 총 물병의 개수 : 3

 

적용

1. N을 2진수로 치환했을 때, 가장 뒤에 있으며 비트가 1인 수를 구한다.

2. N = N - (1번에서 구한 수) 를 하여 비트 1의 개수를 하나 없앤다.   

ex) 00001101(2) - 00000001(2) = 00001100(2)

3. 1~2번을 반복하되 이를 카운트한다.

4. 카운트한 수가 K 이하일 때 프로그램 종료, K 초과면 1을 더한 뒤 1번으로 돌아간다. 

  if count<=K : break;   

  else : N+1 and goto(1번)

 

예제) N=13, K=2       

1번째 1추가 -> 00001101(2) + 00000001(2) = 00001110(2)       , count=3       

2번째 1추가 -> 00001110(2) + 00000001(2) = 00001111(2)       , count=4

3번째 1추가 -> 00001101(2) + 00000001(2) = 00010000(2)       , count=1

 => 3번째 1추가에서 count<=K가 되므로 출력 결과가 3이 나온다.

 

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 result=0;
		
		while(true) {
			int tempN=N;
			int cnt=0;
			while(tempN>0) {
				tempN=tempN-(((~tempN)+1)&tempN);
				++cnt;
			}
			if(cnt<=K) break;
			++N;
			++result;
		}
		System.out.println(result);
	}
}