백준 / 물병 / 1052번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 물병 / 1052번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/1052

 

문제 설명

---

나의 풀이

# 문제의 핵심:
# 1: 물병을 k개 이내로 만들어야한다.
# 2: 물병에서 다른 물병으로 이동할 때는 같은 양의 물이 있어야 가능하다.
# 3: 모든 물병은 1L를 가진채 시작한다.

# 핵심 로직:
# 문제를 자세히 살펴보면 총 물의 양은 2, 4, 6, 8, ... 2^n
# 2의 제곱으로 증가한다 이걸 2진수로 나타내서 2진수에 존재하는 1의 개수가 k개 이내로 존재하면
# 물병을 만들 수 있게 된다.

# 물병을 구하는 함수
def solution(n, k):
    # 최소한으로 들어간 물병의 개수
    answer = 0

    while bin(n).count('1') > k:
        # 물병을 추가한다.
        answer += 1
        # 물병을 추가하므로 1L 공급해준다.
        n += 1

    return answer

if __name__=="__main__":
    # 물병의 개수와 물만 들어있어야 할 물병의 개수
    n, k = map(int, input().split())

    print(solution(n, k))

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/219

[알고리즘] 비트마스크(BitMask)

모든 경우에서 2진 데이터를 사용할 순 없지면 위 문제처럼 2진 데이터를 사용할 수 있을 경우 사용하면 메모리 효율성, 속도(비트의 연산은 빠르기 때문에, 대량의 데이터를 신속히 처리가 가능합니다), 코드의 간결성을 보장할 수 있습니다!