[백준] 8250번 : 물병 - Java

[백준] 8250번 : 물병 ( Gold IIIII )

---

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

 

 

입력

---

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

 

 

출력

---

 

 

풀이

---

브루트포스로 풀었습니다.

비트를 사용하는 문제인데, 처음에 비트를 사용하는문제인지 모르고, 수학적 계산을 통해 풀려다 실패하였습니다.

결국, 수학적 계산을 통해 푸는 방식도 2의 제곱들을 어떻게하여 엮어 이 문제를 풀 수 있을까 생각하였는데,

비트를 사용하면 간단히 풀 수 있는 문제였네요.

비트를 사용하여 푸는방법은 이러합니다.

예를들어, 예제입력 13 2가 들어간다고 치면,

13 => 1101(2)로 십진 => 이진변환이 가능합니다.

여기서, 1을 더하면 14 (1110)이 되고, 물통은 3개가 됩니다. 다시 1을 더하면 15(1111), 다시 1을 더하면 16(10000)이 됩니다. 이렇게 1이 증가할 때 마다 이진수의 1의 갯수가 바뀌는것을 토대로, K의 값보다 같거나, 작아질 때 반복문이 종료되는 트리거를 걸어 정답을 도출하도록 하였습니다.

허나, 이 방법은 이 문제가 시간복잡도를 느슨하게 주었기 때문에 브루트포스 방식으로도 풀리는것일 뿐, 그렇지않다면 비트의 맨뒤에서부터 각 자릿수에 1을 더해가며 1의 갯수가 K의 조건을 만족하는지를 토대로 최적화하여 풀면 될것같습니다.

 

예를 들자면,

1000000 5라고 한다면, 

1000000 = 11110100001001000000(2)입니다. 이 경우 현재 1의갯수는 7이므로, 1의 갯수를 줄이는 방향으로 가야합니다. 즉 Binary Code의 맨 앞자릿수의 1들을 보존하면서, 5개로 만들어야 가장 적은 코스트로 K를 만족시킬 수 있으므로, 맨 뒤에서부터 1을 0으로 만들어나가며 1의 갯수를 줄여야합니다. 따라서, 1의 자릿수인 2^6과, 2^9를 앞자릿수쪽으로 밀어내어 1의 갯수를 5로 만들어야하므로,

6의자리1을 더하여 6의자리 1을 밀어내고 7의자리에 1이 생기면 7의자리 1을 더하고, 반복하면 결국2^6+2^7+2^8+2^10+2^11+2^12+2^13와 같은 꼴이 나오게됩니다.

위와같이 최적화를 하면 더욱 좋은코드가 나올것이지만, 저의 경우에는 브루트포스를 사용하여 풀었습니다.

 

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

class Main{

    public static Stack<Integer> stack = new Stack<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        int answer = 0;

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        boolean isFind = false;
        if(Integer.bitCount(N) > K){
            int target = N;
            for (int i = 0; i < 10000001; i++) {
                target += 1;
                if(Integer.bitCount(target) <= K){
                    answer = i+1;
                    isFind = true;
                    break;
                }
            }
        }else{
            isFind = true;
        }

        if(!isFind){
            answer = -1;
        }

        bw.write(answer + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

긴 글 읽어주셔서 감사합니다.