백준 [1052] 물병 (Python3)

문제 링크 : https://www.acmicpc.net/problem/1052

1052번: 물병

2의 제곱을 이용해 풀 수 있는 문제. 처음에 식을 만들어 문제를 풀었더니 WA를 받았다.
틀린 이유를 찾는 과정에서 1 ~ 10 개의 물병을 최대로 합칠 수 있는 경우에 대해 써본 결과
복잡하게 공식을 쓸 것도 없이 완전탐색을 통해 해결할 수 있단 것을 알았다.

 

N         합치는 과정

1         1 -> 1개
2         1, 1 -> 2 -> 1개
3         1, 1, 1 -> 2, 1 -> 2개
4         1, 1, 1, 1 -> 2, 2 -> 4 -> 1개
5         1, 1, 1, 1, 1 -> 2, 2, 1 -> 4, 1 -> 2개
6         1, 1, 1, 1, 1, 1 -> 2, 2, 2 -> 4, 2 -> 2개
7         1, 1, 1, 1, 1, 1, 1 -> 2, 2, 2, 1 -> 4, 2, 1 -> 3개
8         1, 1, 1, 1, 1, 1, 1, 1 -> 2, 2, 2, 2 -> 4, 4 -> 8 -> 1개
9         1, 1, 1, 1, 1, 1, 1, 1, 1 -> 2, 2, 2, 2, 1 -> 4, 4, 1 -> 8, 1 -> 2개
10        1, 1, 1, 1, 1, 1, 1, 1, 1, 1 -> 2, 2, 2, 2, 2 -> 4, 4, 2 -> 8, 2 -> 2개

 

최종적으로 합칠 수 있는 개수를 종합해보면 N을 이진수로 변환할 때 생기는 1의 개수가
최대한으로 합칠 수 있는 수이다.

 

완전탐색

N을 이진수로 표할 때 생기는 1의 개수를 세어, K보다 크다면 N을 1 더한다.
이 작업을 1의 개수가 K와 작거나 같을 때 까지 반복한다.

 

10^7과 비슷한 값이 나오는 2의 제곱은 23이다. 즉, 2로 나누는 최대 횟수는 23이다.
O(N * 23) 이기 때문에 시간 초과가 날 수 있지만 천만까지 가기 전에 적당한 N을 찾을 수 있단 점과

N이 작으면 23번 이내로 N을 0으로 만들 수 있기 때문에 시간 복잡도는 충분하다 생각했다.

 

하지만, 반복문을 직접 구성하는 것은 생각보다 시간이 오래 걸렸는지 TLE를 받았다.
따라서, N에서 1의 개수를 세는 것을 내장 함수로 처리했고, 통과를 했다.

 

평소 풀듯이 완전탐색으로 해결하는 경우부터 생각해 문제를 풀었다면 1번만 WA를 받았을 텐데 왜 공식을 만들어서 풀었는지를 모르겠다.

 

코드

N, K = map(int, input().split())
a = bin(8)
if N <= K:
    print(0)
else:
    tempN = N
    while True:
        count = bin(N).count('1')
        if count <= K:
            print(N - tempN)
            break
        N += 1