백준 1052번 Python / Greedy

728x90

1052번: 물병

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번

www.acmicpc.net

처음에는 물병의 개수만큼 1의 원소의 배열로 채워서 문제를 해결하려고 했으나 풀지 못했습니다.

계속 생각하던 중에 물병을 합칠수록 1L, 2L, 4L, ... 꼴로 용량이 늘어나는 것을 보고 이진수와 관련이 있지 않을까 생각했습니다. 그 후에도 생각이 잘 떠오르지 않아 구글링을 통해 방법을 찾았습니다.

해결 방식은 다음과 같습니다.

N:3 -> [1, 1, 1] -> [2, 1] = 2^1 + 1

N:5 -> [1, 1, 1, 1, 1] -> [4, 1] = 2^2 + 1

N:7 -> [1, 1, 1, 1, 1, 1, 1] -> [4, 2, 1] = 2^2 + 2^1 + 1

위의 예시와 같이, 2의 제곱으로 표현할 수 있는 수로는 물을 얼마든지 합칠 수 있습니다.

따라서, N을 이진법으로 변환했을 때 1로 나타나는 수의 개수가 최대로 합치고 난 후의 물병 개수로 확인할 수 있습니다.

N:3 -> 11 -> 2개

N:5 -> 101 -> 2개

N:7 -> 111 -> 3개

최종적인 해결 방법은 1의 개수(n의 이진수에서)가 k보다 클 때 n값을 더해가며 반복적으로 비교해주면 됩니다. 정답은 반복적인 비교 과정에서 count 값을 1씩 증가시켜 구했습니다.

n,k = map(int, input().split())

cnt = 0
while bin(n).count('1') > k:
    n += 1
    cnt += 1
print(cnt)

728x90

Study ML