[PS] BOJ1052 물병 ( 비트마스킹 ) With JAVA

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

1052번: 물병

 

 

◎ 문제풀이 

 

비트마스킹을 발상하면 쉽게 풀 수 있는 문제이다. ( 비스트 마스킹 발상이 어렵다.. )

지민이가 가지고 있는 N개의 물병은 1L 씩 채워져 있고, 2개씩 합쳐서 K개 이하로 만들 때, 구매해야 하는 물병의 개수를 구하는 문제이다. 

 

예를 들어, 지민이가 물병을 13개 가지고 있고 한번에 2개를 옮길 수 있다고 가정해보자.

 

 

 

 

 

물병 13개를 합치면 3개의 물병이 남는다. ( 8L, 4L, 1L ). 물병은 합치면 2ⁿ L의 물병이 나오는 것이다. 

 

8, 4, 1을 2진수로 표현하면 1101이고, 이는 13의 이진수 표현이다.

 

여기서 문제를 다시 정의하면,

N의 이진수의 1의 개수가 K개 이하로 만들 때, 구매해야 하는 물병의 개수를 구하는 문제인 것이다.

 

물병 하나를 구매하면 1L이므로, 0001이 추가된다. 그럼 물병을 1개 구매해보자. 

 

1101 + 0001 = 1110 ( 1개 구매 )  : 1110의 1의 개수는 아직 2(K)보다 크다. 그러므로 물병 1개를 더 구매한다. 

1110 + 0001 = 1111 ( 1개 구매 ) : 1111의 1의 개수는 아직 2(K)보다 크다. 그러므로 물병 1개를 더 구매한다. 

1111 + 0001 = 10000 ( 1개 구매 ) : 10000의 1의 개수는 2(K)보다 작으므로 더 이상 물병을 구매할 필요가 없다. 

 

그럼 정답은 3이 된다. 

 

 

◎ 코드

import java.io.*;
import java.util.*;

public class Main{
    
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        
        int ans = 0;
        
        while(Integer.bitCount(n) > k){ // n의 1의 개수 구하기
            
            ans += 1; // 물병 한개 추가
            n += 1; // 0001 더하기
            
        }
        
        System.out.println(ans);

    }
}

 

 

위 코드는 정답 코드이긴 비트연산자를 활용하면 더 좋은 성능을 낼 수 있다.

 

1110 + 0001 = 1111

1111  + 0001 = 10000 , 0001 씩 더해서 하나씩 연산하는 것보다

 

1110 + 0010 = 10000,  0010을 더해 연산 한번에 끝내는 것이 좋다. 

0010은 1110에서 가장 오른쪽에 있는 1을 의미한다. 이를 가장 낮은 유효비트라 부른다. 

 

가장 낮은 유효비트는 N & (-N) 연산으로 구할 수 있다. 

 

1101 + 0001 (가장낮은유효비트) = 1110 ( 1개 구매 )  : 1110의 1의 개수는 아직 2(K)보다 크다. 그러므로 물병 1개를 더 구매한다.

1110 + 0010 (가장낮은유효비트)  = 10000( 2개 구매 ) : 10000의 1의 개수는 2(K)보다 작으므로 더 이상 물병을 구매할 필요가 없다. 

 

물병 3개를 구매하여, 한번에 옮길 수 있게 된다. 

 

 

import java.io.*;
import java.util.*;

public class Main{
    
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        
        int ans = 0;
        
        while(Integer.bitCount(n) > k){
            
            ans += n & (-n);
            n += n & (-n); 
            
        }
        
        System.out.println(ans);

    }
}