[Python] 1052 - 물병 (실버1)

1. 문제 설명

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

1052번: 물병

 

---

2. 아이디어

이 문제를 처음 접했을 때, 규칙성을 파악하다가 비트 연산을 쓰면 편하겠다 싶긴 했는데

비트 연산을 많이 안 써봤던 터라 컨트롤하는데 애 좀 먹었었다.

'여기서 대체 왜 비트가 나오나요?'라는 질문을 할 수 있는데 아래의 그림을 보면 이해할 수 있다.

 

그림을 보면 2의 거듭제곱은 곧 1병으로 합칠 수 있음 의미한다.

N이 2의 거듭제곱으로 주어진다면 추가해야 하는 물병 수는 K와 상관없이 무조건 0이 된다.

(K는 0이 아닌 자연수이기 때문에)

 

다시 위의 그림을 보자.

N이 9일 때, 총 물병의 수는 2개까지 줄일 수 있다.

2진수로 값을 표현해보면 9는 '0000 1001(2)'는 1이 2개가 있고, 16은 '0001 0000(2)'은 1이 1개가 있다.

2진수에서 1의 갯수가 최대로 합칠 수 있는 물병의 수가 됨을 알 수 있다. 이게 우연일까?

아니다. 모든 물병은 2의 제곱수 만큼의 용량을 가지기 때문에 발생한 일이다.

따라서 물병이 9개이고 이를 한 병에 합치기 위해서는 0000 0111(2), 7(10)만큼 더해주면 되는 것이다.

 

기억해야 할 것은 2진수로 표현했을 때, 1의 개수가 곧 물병 갯수를 의미한다는 것이다.

 

위의 규칙을 기억하고 무작위의 어떤 수를 통하여 방법을 도출해보자

0100 1011 0110 1101(2)이란 수가 주어졌다면 현재 물병은 9개가 존재한다는 것을 알 수 있다.

추가해야 하는 물병수를 최소로 해야하기 때문에 K가 9부터 1까지 내려갈때 N값의 변화를 보자.

K	N
9	0100 1011 0110 1101
8	-
7	0100 1011 0111 0000
6	-
5	0100 1011 1000 0000
4	-
3	0100 1100 0000 0000
2	0101 0000 0000 0000
1	1000 0000 0000 0000

어렵지 않은 내용이다.

가장 작은 자릿수의 1을 없애고 다시 1의 개수를 판단했을 때, K보다 작거나 같으면 된다.

위의 아이디어를 떠올리고 비트 마스크를 사용하겠다는 발상이 어렵지,

개념만 이해한다면 굉장히 쉬운 문제가 된다.

 

bin(), count() 함수를 쓰면 훨씬 짧게 쓸 수 있지만,

나는 비트 마스크를 연습할 겸 함수를 사용하지 않고 풀이했다.

 

---

3. 코드

def solution():
    n, k = map(int, input().split())
    total, tmp = 0, 1

    while True:
        num, cnt = n, 0
        while True: # 1개수 판단
            if num & 1:
                cnt += 1
            if num == 0 or num == 1:
                break
            num >>= 1

        if cnt <= k:
            print(total)
            return

        while True:
            if n & tmp != 0:
                n += tmp
                total += tmp
                break
            tmp <<= 1
        

solution()