[BOJ] 1052 - 물병(Python)

문제

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

풀이

같은 물병은 하나의 더 큰 물병으로 합쳐진다는 점에서 처음 주어진 n을 2진법으로 나타내면 초기에 만들 수 있는 물병의 개수를 알 수 있다.

첫번째 풀이
2진법으로 표현하고 나면, 해당 비트가 가리키는 인덱스에 따라, 현재 인덱스에서 다음 인덱스로 물통을 변환시키는데 필요한 물의 양을 알 수 있으므로, 계속 비트를 옮겨주면서 정답일 때까지 반복한다.

두번째 풀이
결국, 첫번째 풀이에서 물통을 줄이는데 중요한 것은, 현재 인덱스에서 값을 올릴 때, 다음 인덱스가 1일 때만 전체 물통의 개수가 줄어든다는 것이다. 그러므로, 반복문을 통해 정답을 구할 필요 없이, 이진법으로 된 string을 한번만 스캔하면 정답을 알 수 있다.

코드

#2번째 코드 : 1번의 string scan으로 끝내기
n,k = map(int,input().split())
answer = 0
n = bin(n)[2:]
cnt = n.count('1')
if cnt > k:
    idx = len(n)
    encount = -1
    while cnt-encount > k and idx > 0:
        idx -= 1
        if n[idx] == '1':
            encount += 1
    answer = (1<<(len(n)-idx)) - int(n[idx:],2)
print(answer)


#1번째 코드 : 정답일 때까지 반복
# n,k = map(int,input().split())
# answer = 0
# n = list(map(int,bin(n)[2:]))
# n=n[::-1]+[0]

# cnt = n.count(1)
# idx = 0
# answer = 0
# while cnt > k:
#     if n[idx] == 1:
#         answer += (1<<idx)
#         cnt += 1
#         n[idx] += 1
#         i = idx
#         while i+1 < len(n):
#             if n[i] == 2:
#                 cnt -= 1
#                 n[i+1] += 1
#                 n[i] = 0
#             i += 1
#     idx += 1
# print(answer)

이론상 10000번 이상 반복을 돌릴 수도 있는 1번 코드보다 2번 코드가 훨씬 빠를거라 예상했는데, 막상 제출해보니 시간은 똑같이 44ms로 나와서 아쉬웠다. 최적화한다고 해도 큰 차이가 없을 것 같아서 연산 최적화는 추가로 진행하지 않았다.