백준 1052 - 물병

1052번: 물병 (acmicpc.net)

1052번: 물병

 

요즘 근래 너무 골드3 문제에 치여서 좀 쉬운 문제를 풀면서 다시 코테 흥미를 높여볼까 생각하면서 실버1 문제를 건드려보았다.

근데 이게 뭔가 싶은데... 누가봐도 그리디 문제인데, 뭐 도통 이해가 안되는 문제를 만나서 한참을 헤메게 되었다. 이 문제를 스터디원들과 꼭 공유해보고자 블로그를 작성한다.

 

※ 문제의 규칙성

이 문제는 규칙을 발견하면 사실상 문제가 끝난다고 보면된다. 코드도 정말 간단하기 때문에... 충격적이었다.

 

예를 들어 13 2 입력을 받은 경우를 생각해보자.

총 1L씩 들어있는 13개의 물병을 아래와 같이 진열해보자.

13 -> 1 1 1 1 1 1 1 1 1 1 1 1 1

 

이제 이 물병들을 두 개씩 묶어서 계속 변형시켜보자.

2 2 2 2 2 2 1

4 4 4 1

8 4 1

 

여기서 물병을 하나 더 구매하게 되면

8 4 2

두 개를 더 구매하게 되면

8 4 2 2

8 4 4

8 8 

16

 

이렇게 줄여나갈 수 있다. 이렇게 총 2개보다 더 낮은 수의 물병을 만들 수 있게 되는 셈이다.

여기서 정말 큰 충격적인 사실이 나오게 되는데, 13을 이진법으로 고쳐보면 1101이다.

결론적으로 추가로 물병을 구매하지 않을 경우에 나올 수 있는 마지막 물병 수가 이진법의 1의 갯수와 동일한 셈이다.

1101에서 계속 추가적으로 n의 갯수를 늘려가면서 k 아래까지 물병 갯수를 줄여나가면 되는 것이므로, while문 속에서 n+1로 처리가 가능하다.

 

자 그렇다면 여기서 이진법 문자열로 숫자를 표현할 수 있는 python의 bin 내장함수와 해당 문자의 갯수를 표현해 줄 수 있는 count 내장함수를 사용하게 되면 매우 쉽게 문제를 해결할 수 있다.

import sys
input = sys.stdin.readline

n, k = map(int, input().split())

result = 0
while bin(n).count('1') > k:
    n += 1
    result += 1

print(result)

 

기존에는 마지막 예시가 잘 이해가 되지 않았다. 그냥 2L와 1L 물병 두개를 더해서 3L로 만들면 되는 것이 아닌가 생각했는데, 마지막 문장을 통해서 같은 L 수의 물병들을 선택해야 한다는 점을 깨닫고, 그렇다면 2개씩이니까 이진법을 떠올려보게되었다.

 

문제를 풀고 나서 구글링을 해보았는데, 거의 대부분 이 방식으로 문제를 풀고 있었고, 시간을 더욱 줄이기 위해 비트마스킹을 이용한 방법도 있어 굉장히 신박하다고 생각이 들었다. 그리디 문제의 경우는 대부분 문제풀이가 일정할 수밖에 없는 것이 어떤 규칙성을 대놓고 의도해서 문제를 제작하다보니 그런게 아닐까하는 생각이 드는 문제였다.