Algorithm/Baekjoon

[백준] 8250번 : 물병 - Java

Ho-home 2024. 8. 15. 15:13

[백준] 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();
    }
}

 

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