[ boj : 1052 ] 물병

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

1052번: 물병

정말 오랜만에 포스팅 합니다.

맥북에어를 사고 첫 포스팅인데 사실 그동안 글쓰는 것에 대해 많은 고민이 있어서 생각좀 정리하고 다른 바쁜일도 생겨서 어쩌다가 오랜만에 글을 올립니다.

 

해설 : 먼저 처음에 큐를 사용해서 풀면 되겠지 했습니다. priority queue 를 선언한 후 하나빼고 top에 있는 아이 비교해서 동일하면 다시 pop 해서 1더해주고 집어 넣고,,,근데 우리가 코딩을 하다보면 이건 아닌것 같은데 하는 느낌이 확 올때가 있죠.

 

바로 저 방법이 그런 느낌이었습니다. 왜냐면 생각하는 것만큼 구현이 간단하지가 않기 때문입니다.

그래서 다시 생각해보았습니다.

 

먼저 물병 n 개가 처음 주어지면 n 리터이라는 뜻입니다. 이를 그러면 어떻게 '표현'할 수 있을까요??

이진수로 표현해보기로 합시다.

 

7 = 111(2)

10 = 1010(2) 

 

이런식으로 표현해줄 수 있겠죠. 그러면 1이라고 표시되어있는 자리는 2^n 의 물의 양을 뜻하는 것입니다.

무슨 말이냐면 7=111(2) 이니 1L + 2L + 4L 로 표현이 가능하고, 10 = 1010(2) 이니 2L + 8L 로 표현가능 한 것입니다.

 

근데 우린 문제에서 k 병 이하로만 만들면 되죠???그러면 그냥 직접 1씩 더하면서 몇병이 필요한가를 확인해 보는 것입니다.

예를 들어서 

 

n=7, k=2 라고 가정을 해봅시다.

그럼 우린 1L + 2L + 4L 이렇게 3병이 7L 를 이루고 있다는 것을 알고 있는 상태죠.

그러나 2병으로 만들어야 합니다. 그럼 처음 7병인 상태에서 +1 해서 총 8병으로 만들어 보자는 것이죠.

 

8 = 1000(2) 즉, 처음 8병으로 시작하면 결국 1병으로 만들 수 있게 됩니다.

그러므로 정답은 (+1한 8병)-(처음 n병) = 1병 이 정답이 되는 것 입니다.

 

n 은 10^7 이하이고 , k 는 1000보다 작으니 시간초과가 발생할 일도 없겠죠??

 

import java.io.*;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static FastReader scan = new FastReader();
    public static void main(String[] args) {
        int n,k;
        n=scan.nextInt();
        k=scan.nextInt();

        int cnt=n;
        while(true)
        {
            if(solve(cnt)<=k)break;
            cnt++;
        }
        System.out.println(cnt-n);
    }
    static int solve(int x) {
        int cnt=0;
        while(x>0){
            if((x&1)==1)
                cnt++;
            x/=2;
        }
        return cnt;
    }
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;

        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }
        String next(){
            while(st==null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        int nextInt(){
            return Integer.parseInt(next());
        }
        double nextDouble(){
            return Double.parseDouble(next());
        }
        long nextLong(){
            return Long.parseLong(next());
        }
        String nextLind(){
            String str="";
            try{
                str=br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}