1502

날짜 : 2022. 11. 22

사용 언어 : python

 

문제

 

 

코드

import sys

n, k = map(int, sys.stdin.readline().split())
cnt = 0

while bin(n).count('1') > k:  # n을 2진수로 표현 시 1의 개수가 k보다 작은 경우
    n += 1
    cnt += 1

print(cnt)

 

 

풀이

- n에 대해서 전부 합쳤을 때 하나하나 표현한다면 다음과 같다.

N = 2 : [1, 1]  ->  [2]  => 1 (10)

N = 3 : [1, 1, 1]  ->  [2, 1]  => 2 (11)

N = 4 : [1, 1, 1, 1]  ->  [4]  => 1 (100)

N = 5 : [1, 1, 1, 1, 1]  ->  [4, 1]  =>  2 (101)

N = 6 : [1, 1, 1, 1, 1, 1]  -> [4, 2]  =>  2 (110)

N = 7 : [1, 1, 1, 1, 1, 1, 1]  -> [4, 2, 1]  => 3 (111)

N = 8 : [1, 1, 1, 1, 1, 1, 1, 1]  ->  [8]  => 1 (1000)

이렇게 정리한 값이 도출되고, 이 값들은 N을 2진법으로 표현했을 때 1의 개수와 동일하다.

- 그러므로 N을 2진수 문자열로 변환 후 1의 개수가 k값보다 크다면 N값을 1씩 추가(물통을 추가)하는 것을 반복하여 k값보다 처음으로 작거나 같아지는 경우 해당 반복문을 탈출하는 방식으로 문제를 풀이하면 된다.

 

 

 

알게된 점

- 

 

 

참고 사이트

- https://velog.io/@kcs05008/알고리즘-물병-백준-1052

[알고리즘] 물병 백준 1052 python