백준 - 1052 물병

백준 - 1052 물병

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

솔직히 흥미로운 문제였다. 그리고 풀면서 많이 배웠다. 시뮬레이션 문제처럼 풀면 복잡할 것 같다.

★ 풀이

결국 문제에서 원하는 것은 물병을 합칠 수 있을만큼 합쳐서 k개 보다 작게 만들 수 있는 최소한의 추가물병의 개수이다.

여기서 질문 몇가지 하겠다.

1. 물병 7개를 최대한 합치면 몇개까지 줄일 수 있을까? 답은 3개다.

2. 물병 10개를 최대한 합치면 몇개까지 줄일 수 있을까? 답은 2개다.

3. 물병 14개를 최대한 합치면 몇개까지 줄일 수 있을까? 답은 3개다.

일일이 구하면 귀찮다. 이미 눈치챈 사람도 있겠지만 물병 2^n개는 ( 1 2 4 8 16 25.... ) 결국 물병 하나로 만들 수 있고, 이것은 결국 n을 2진수로 변환했을때 1의 개수를 구하면 그것이 바로 최대한 줄일 수 있는 물병 개수인 것을 알 수 있다.

자, 이제 다했다. 비트 마스크를 생각하고 최대한 줄일 수 있는 물병의 개수가 k보다 많을 때마다 편의점에서 물병을 하나씩 추가하면 언젠가는 답을 구할 수 있다.

+ Integer.bitCount()를 사용하면 10진수를 2진수로 바꾸었을 때 비트 1의 개수를 구할 수 있다.

★ 소스 코드

import java.io.*; import java.util.*; // 좋은 코드 흡수하기! public class Main { static BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); static int n,k; public static void main(String[] args) throws IOException { StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); k = Integer.parseInt(st.nextToken()); // k개보다 같거나 작도록 줄일 수 있겠나? int ans = 0; while(Integer.bitCount(n+ans) > k) { ans++; } System.out.println(ans); } }

from http://sweet-smell.tistory.com/93 by ccl(A) rewrite - 2021-11-17 07:28:08