[백준 - Python] 1052. 물병 (그리디)

https://www.acmicpc.net/problem/1052

1052번: 물병

 

코드

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

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

print(cnt)

 

문제 이해부터 어려웠다.

 

정리하면, N개의 물병을 K 개의 물병으로 재분배 하여, 한번에 물병을 옮기려고 하는 것이고

물병은 추가 구매가 가능한 상황에서

추가 구매해야 하는 물병의 최소 개수를 구하는 문제였다.

 

물병에 들어갈 수 있는 물의 양은 무한대라고 하였고,

상점에서 구매할 수 있는 물병의 개수도 제한이 없기 때문에

사실상 정답이 존재하지 않는 상황은 존재할 수 없다.

(처음 문제를 접했을 때, 정답이 없는 상황이 가능한건 지 고민을 오래했다...;;)

 

예제로 주어진 입출력을 보면서 한 생각은

N<K 인 경우에는 물병을 추가만 하기

N==K 인 경우에는 그대로 가져가기

N>K 인 경우에는 N//2 + (나머지가 있다면) 나머지 한 값이 K보다 큰지 작은지 파악하고,

해당 값이 홀수인지 짝수인지, K가 N의 절반보다 큰지 작은지 나누는 식으로

경우의 수를 파악하고 구현을 시도했지만 실패했다.

 

다른 분들의 코드와 아이디어를 참고해서 보니까 코드가 굉장히 짧았다.

아이디어는 떠올리기 꽤 어려운 수준이었다.

 

결론부터 이야기하면,

n을 2진수로 표현했을 때, 1의 개수가 물통의 개수임을 알고

해당 아이디어를 바탕으로 문제를 풀어야 했다.

 

문제의 해결법을 생각하다보면,

물의 양이 1, 2, 4, 8, 16 ... 과 같이 2의 제곱 형태일 때에만 합칠 수 있다는 점을 통해

이진수의 1의 개수를 활용할 생각을 떠올리는데 도움을 받을 수 있지 않았을까 하는 생각이 든다.

 

따라서, 최종 물병의 수가 K보다 크게 되면

즉, n을 이진수로 변환했을 때 K보다 크게 되면 n에 1을 더해서

다시 이진수로 표현해 1의 개수를 세고

K보다 작아지는 순간까지 반복한다.

 

여기서 1을 더할 때, 순차적으로 더하다 보면 0이 있는 자리에 1을 더하면서

1을 오히려 늘리는 상황까지도 전부 훑어봐야하는 비효율적인 상황이 발생한다.

n의 이진수를 왼쪽부터 살펴보면서 1이 최초로 등장하는 자리에 1을 더해주면

불필요한 확인의 과정을 단축시킬 수 있다.

 

n, k = map(int, input().split())
answer = 0
while bin(n).count('1') > k:
    idx = bin(n)[::-1].index('1')
    answer += 2**idx
    n += 2**idx

print(answer)

 

index 함수는 특정 문자의 위치를 왼쪽부터 찾아서

해당 위치의 인덱스 값을 반환하는 함수이므로

bin 함수로 만들어진 이진수 문자열을 뒤집은 후에 index 함수로 1의 위치를 찾아

해당 위치에 숫자를 더해주었다.

 

 

확실히 연산 속도가 빠르다...

 

파이썬에서 bin() 함수를 이용해 10진수를 2진수로 바꿀 수 있다.

문자열로 반환된다.

(binary의 앞 세글자)

 

 

참고 자료

https://latte-is-horse.tistory.com/364

https://velog.io/@rhdmstj17/%EB%B0%B1%EC%A4%80-1052%EB%B2%88-%EB%AC%BC%EB%B3%91-python-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9