백준 물병 1052번 파이썬

 

 

1052번: 물병

 

 

접근

이진법으로 접근해야 한다.

 

코드

입력받은 숫자 N을 bin() 메서드로 이진수로 변환하고 1의 개수를 구한다.

이 1의 개수가 해당 숫자 N 에서 만들 수 있는 물병의 갯수가 된다. 예를 들어 N 이 3이라면, 세 개의 물병에서 문제의 조건대로 만들 수 있는 물병의 개수는 2개가 된다.

그래서 while bin(N).count('1') > K: 이라는 조건식을 만들 수 있다. 우리가 만들고자 하는 물병의 개수는 K 를 넘지 않아야 하니까. 

 

# 1. 일일이 다 더해본다.

약간 브루트 포스 방식이 아닐까 싶다. 

N, K = map(int, input().split())

added_bottle = 0

while bin(N).count('1') > K:
    N += 1
    added_bottle += 1

print(added_bottle)

 

# 2. 이진법 접근

설명은 주석에 달아놓았다 ㅈㅅ

N, K = map(int, input().split())

added_bottle = 0

while bin(N).count('1') > K:
    idx = bin(N)[::-1].index('1')  # N에서 1이 처음 나타난 index 를 구하기 위해 뒤집는다.
    bi_to_decimal = 2 ** idx  # 해당 인덱스(이진수)를 10진수로 변환
    added_bottle += bi_to_decimal
    N += bi_to_decimal

print(added_bottle)