[Java] BaekJoon1052 - 물병

• 문제 링크

아래는 물병n개를 가지고 있고, 새로운 물은 하나도 구매하지 않았을 때를 가정했을 때의 결과다.

2 => [1,1] => [2] => 1병

3 => [1,1,1] => [2,1] => 2병

4 => [1,1,1,1] => [2,2] => [4] => 1병

5 => [1,1,1,1,1] => [2,2,1] => [4,1] => 2병

6 => [1,1,1,1,1,1] => [2,2,2] => [4,2] => 2병

7 => [1,1,1,1,1,1,1] => [2,2,2,1] => [4,2,1] => 3병

8 => [1,1,1,1,1,1,1,1] => [2,2,2,2] => [4,4] => [8] => 1병

위의 공식을 보면, 2진수의 배수일 경우에만 물병을 구입하지 않고 해결 할 수 있는 것을 확인 할 수 있었다.

문제 내에서의 함정이 숨어있으므로, 이를 조심해서 풀자.

• Scanner와 배열을 이용하여 처음 풀었을 당시의 코드:

  import java.util.Scanner;
    
  public class Main {
    
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
      int x = 0;
      int n = scanner.nextInt();
      int k = scanner.nextInt();
    
      while (true){
    
        if(count(n+x) <= k) {
          break;
        }
    
        x++;
      }
    
      System.out.println(x);
    }
    
    public static int count(int n){
      int cnt = 0;
    
      while (n > 0){
        if(n%2 ==1) cnt++;
        n /= 2;
      }
      return cnt;
    }
  }
    
  

  • n의 값이 0이 되기 전 까지 n을 2로 나누는데, 이 때 나머지가 1일 경우, 지민이가 들고 갈 물 병의 갯수를 구하기 위한 cnt 값을 올리도록 count메소드를 작성하였다.

      public static int count(int n){
        int cnt = 0;
        
        while (n > 0){
          if(n%2 ==1) cnt++;
          n /= 2;
        }
        return cnt;
      }
    }
    

  • 위의 count 메소드의 return 값을 K와 비교해, K보다 클 경우, 계속해서 count를 반복하도록 반복문을 작성하였다. 이 때, 지민이가 구매 할 물병의 개수 x의 값을 올리도록 하여, 총 구매해야하는 물병의 갯수를 출력하도록 만들었다.

    • 결과:

• BufferedReader와 메소드를 변경 한 코드:

  import java.io.*;
  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());
    
      System.out.println(result(n, k));
    
      br.close();
    }
    
    public static int count(int n) {
      int cnt = 0;
    
      while (n > 0) {
        cnt += n & 1;
        n >>= 1;
      }
      return cnt;
    }
    
    public static int result(int n, int k) {
      int x = 0;
    
      while (count(n + x) > k) {
        x++;
      }
    
      return x;
    }
  }
    
  

  • 원래는 n을 나누고, 나머지를 구하는 식을 비트 연산자로 변경을 하였다.

    public static int count(int n) {
        int cnt = 0;
        
        while (n > 0) {
          cnt += n & 1; 
          // n&1의 경우, 10진수를 2진수로 변경 하여, 값을 서로 비교 해, 값이 같은 1일경우만 1을 반환한다.
          // ex) 10 & 1 => 1010 & 0001 = 0000 이기 때문에, cnt += 0이 된다.
          // 위와 같이 풀어보면, 짝수는 0을 반환하고 홀수는 1을 반환하는 것을 볼 수있는데 
    			// 결과적으로, if(n%2 == 1)cnt++; 와 같은 결과값을 가지게 된다.
              
          n >>= 1;
          // n >>= 1 의 경우도 위와 마찬가지로, 10진수를 2진수로 변경하여, 값을 오른쪽으로 1번 밀어준다.
          // ex) 10 >>=1 => 1010 >>= 1 = 0101 와 같은 결과가 나오는데, 0101을 10진수로 변경하면
          //     5가 나오게 된다. 이도 마찬가지로, 결과적으로는 n /= 2; 와 같은 결과를 가지게 되는 것이다.
        }
        return cnt;
      }
    

    • 결과: