물병 ( 1052 번 )

1052번: 물병

 

---

🧠 알고리즘

• 그리디 (이진수 표현 기반 + 최소 증가 연산)

 

✔️ 동작 방식

• 정수 n을 2진수로 변환하고, 1의 개수(water_count)를 센다.
• water_count가 k 이하라면 종료.
• water_count > k인 경우 → 이진수의 오른쪽(하위 비트)부터 1을 찾아 해당 자리에 해당하는 값(2^idx)을 더해준다.
• 위 과정을 반복하여 n의 이진수 표현에서 1의 개수가 k 이하가 될 때까지 수행.
• 누적된 증가값(answer)을 출력한다.

---

 

🧾 코드

import sys

def _cr_count(number):
    eizin, water_count = [], 0
    while True:
        na = number % 2
        if na == 1:
            water_count += 1

        eizin.append(str(na))                

        number //= 2
        if number == 0:
            break
    
    return ''.join(eizin[::-1]), water_count


def _main(n, k):
    answer = 0

    while True:
        eizin_num, water_count = _cr_count(n)
        if water_count <= k:
            break
        else:
            for idx in range(len(eizin_num) - 1, -1, -1):
                if eizin_num[idx] == '1':
                    idx = (len(eizin_num) - 1) - idx
                    answer += (2 ** idx)
                    n += (2 ** idx)
                    break

    return answer

n, k = map(int, sys.stdin.readline().rstrip().split())
print(_main(n, k))

---

 

⏱️ 시간 복잡도

while True : 조건 만족시 까지 반복 ( 선형 시간 복잡도 )
	eizin_num, water_count = _cr_count(n) : 이진 변환 및 체크 함수 ( 로그 시간 복잡도 )
  
>>> 매 반복마다 비트 전체를 스캔하지 않아도 되어 로그 시간 복잡도로 수렴하게됨!!

해당 알고리즘 시간 복잡도 : 로그 시간 복잡도 ( O(log n) )