[백준] S1 1052 물병 (java)

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

1052번: 물병

 

풀이

 

이진수로 바꾸면 물병이 몇개 필요한지 쉽게 알 수 있다.

예제에서 N = 3, K = 1 일때,

N = 3을 이진수로 표현하면 11(2) 이다. 여기서 1의 개수가 곧 물병의 개수이다. K = 1이므로 물병은 1개 여야만한다. 따라서 가장 쉬운 방법은 1을 더해서 100(2) 로 만드는 것이다. 즉 1개의 물병만 사면 한번에 K = 1개의 물병으로 옮길 수 있게 된다.

다른 예를 들어보자.

만약 N = 21, K = 2 일때,

N = 21을 이진수로 표현하면 10101(2) 이다. 여기서 K = 2 이므로 1을 2개로 만들기 위해서 11000(2)으로 만들어야 하는것이다. 11(2)를 더해야 한다.  즉 답은 3.

이를 통해 규칙을 정리하면,

1) N을 이진수로 표현

2) 왼쪽부터 1의 개수가 K개가 된다면 그 뒤의 내용들을 모두 0으로 만들기 위해 모종의 값을 더해야 하고, 그 모종의 값이 곧 정답이 되는 것이다.

3) 2)를 구하기 위해 1을 채워넣고 1을 더한 후 xor 하는 방식을 구현했다. <- 더 좋은 방법이 분명 있을것이다.

4) 쓰다 보니 다른 좋은 방법을 찾아 버렸다. 그냥 11000(2) 에서 10101(2) 을 빼면 답이 나온다. 근데 11000을 구하는게 또 머리써야 하므로 그냥 두자.

 

주의사항

 

1) 만약 정답이 없을 경우에는 -1을 출력한다. <- 뻥이다. 정답이 없는 경우가 존재하지 않는다.

 

package com.baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StringReader;
import java.util.StringTokenizer;

public class BJ_S1_1052_물병 {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N,K;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		K = Integer.parseInt(tokens.nextToken());
		String binaryN = Integer.toBinaryString(N);
		int ones = 0;
		for(int i=0; i<binaryN.length(); i++) {
			if(binaryN.charAt(i) == '1') {
				ones++;
			}
		}
		
		int cnt = 0;
		int point = 0;
		if(ones <= K) {
			System.out.println(0);
		}else {
			for(int i=0; i<binaryN.length(); i++) {
				if(binaryN.charAt(i) == '1') {
					cnt++;
					if(cnt == K) {
						point = i;
						break;
					}
				}
			}
			String stringAnswer = binaryN.substring(point);
			int answer = Integer.parseInt(stringAnswer, 2);
			int temp = 0;
			for(int i=0; i<binaryN.length()-point; i++) {
				temp = temp << 1;
				temp = temp+1;
			}
			answer ^= temp;
			answer = answer+1;
			System.out.println(answer);
		}
	}

	static String src =
			"5 1";
}

 

 

후기

 

보자마자 이진수를 이용해 풀어야 한다고 생각했다. 사람들이 많이 안 푼 문제이지만 생각보다 좋은 문제인것 같다.

이진수의 표현을 Integer.toBinaryString(N)으로 문자열로 바꿀수 있다는 점도 처음 알게되었으며,

Integer.parseInt(String, 2) 가 2진수 문자열을 10진수로 바꾼다는 것도 처음 알게 되었다. 정말 배울점이 많은 문제였다.