[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1052번, 물병

문제 링크

1052번: 물병

 

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 모든 물병은 1리터씩 들어가 있습니다.

2. 물병에 들어있는 리터가 같아야 합칠 수 있습니다.

3. 새로운 물병을 살 수 있으며, 1리터가 들어있습니다.

4. 물이 들어있는 K개의 물병을 만드는 데 상점에서 사야하는 물병의 최소값을 결과로 출력합니다.

5. 정답이 없을 경우 -1을 결과로 출력합니다. (※ 정답이 없는 경우 존재 X)

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. N을 2진수 형태로 만들어서, 물병을 사는 과정을 진행합니다.

 

3. 구매한 물병의 개수를 결과로 출력합니다.

 

 

2진수로 만들기

 

Integer.toBinaryString()을 이용해서 N의 값을 2진수로 바꿉니다.

 

2진수로 바꾸었을 때 1의 개수는 물병을 최대로 합칠 때, 물이 채워져있는 물병의 개수입니다.

 

N = 7일 때

 

1의 개수 ≤ K

 

모든 물병을 합치기 전에 K개의 물병을 만들 수 있으므로 구입할 물병 X

 

1의 개수 > K 

 

모든 물병을 최대한 합쳐도 K개보다 많은 물병이 존재하므로 물병을 구입해서 더 합쳐야 합니다.

 

구매하는 양 구하기

 

2진수에서 '1'을 K개로 만들어야합니다.

 

N = 7K = 12진수 : 111

 

'1'를 1개로 만들려면

 

1000의 형태로 만들어야 합니다.

 

1000의 형태로 만들기 위해 필요한 값1000(8) - 111(7) = 1

 

1이 필요하기 때문에 물병을 1개만 사면 됩니다.

 

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N = 13

K = 2

 

2. N을 2진수 형태로 만들어서, 물병을 사는 과정을 진행합니다.

 

13(N)의 2진수 형태

 

1101

 

 

1의 개수(3) > K(2) 만족

물병을 구매해서 합치는 과정을 더 진행해야합니다.

 

물병을 2개로 만드려면 1101에서  101을 1000의 형태로 만들어야 합니다.

 

그러면 1000의 형태의 물병이 2개가 되어서 K개를 만들 수 있습니다.

 

101 -> 1000으로 만들기

 

1000(8) - 101(5) = 3

 

1L 물병 3개를 구매해야한다.

 

3. 구매한 물병의 개수를 결과로 출력합니다.

 

구매해야하는 개수 : 3개

3을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Integer.toBinaryString을 이용하여 N을 2진수의 형태로 변경하였습니다.
• Integer.bitCount을 이용하여 2진수에서 '1'의 개수를 구하였습니다.
• '1'의 개수에 따라 물병의 개수를 구매하거나 구매하지 않는 경우로 나뉘어 탐색합니다.
• 구매할 경우, 만들어야 할 형태를 만들기 위해서 구매하는 물병의 개수를 구합니다.
• 물병을 구매한 횟수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

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

public class Main{
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int answer = 0, index = -1;
        String bitN = Integer.toBinaryString(N);	//N ▶ 2진
        int ones = Integer.bitCount(N);	//2진수 1의 개수
        if(ones > K){	//1의 개수 > K 일 때
            //K번째 '1'을 기준으로 만들어야 하는 형태의 위치 구하기
            for (int i = 0; i < bitN.length(); i++) {
                if (K == 0) {
                    index = i;
                    break;
                }
                if (bitN.charAt(i) == '1')
                    K--;
            }
            String temp = bitN.substring(index);	//바꿔야 하는 값
            int t = Integer.parseInt(temp, 2);	//바꿔야 하는 값의 10진수 값
            /*
            바꿔야 하는 값이 0이 아닐 때
            Math.pow(2, bitN.length() - index) : 만들어야 하는 형태의 10진수 값
            t : 바꿔야 하는 값에 10진수 값
            Math.pow(2, bitN.length() - index) - t : 물병을 사야하는 개수
            */
            if (t != 0)
                answer = (int) (Math.pow(2, bitN.length() - index) - t);
        }
        bw.write(answer + "");		//물병 구매 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}