BaekJoon 1052번: 물병, 그리디 알고리즘(Greedy algorithm) 문제

이번에는 BOJ 1052번 물병 문제를 C++ 언어를 이용해서 풀이해 봤습니다. 문제 설명 지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다. 물은 다음과 같이 재분배한다. 먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그다음에 한 개의 물병에 다른 한쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속한다. 이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다. 예를 들어, N=3이고, K...

원문링크 : BaekJoon 1052번: 물병, 그리디 알고리즘(Greedy algorithm) 문제