백준 1052 물병 c++ (탐욕법)

문제 출처 : https://www.acmicpc.net/problem/1052

1052번: 물병

문제

지민이는 N개의 물병을 가지고 있다. 각 물병에는 물을 무한대로 부을 수 있다. 처음에 모든 물병에는 물이 1리터씩 들어있다. 지민이는 이 물병을 또 다른 장소로 옮기려고 한다. 지민이는 한 번에 K개의 물병을 옮길 수 있다. 하지만, 지민이는 물을 낭비하기는 싫고, 이동을 한 번보다 많이 하기는 싫다. 따라서, 지민이는 물병의 물을 적절히 재분배해서, K개를 넘지 않는 비어있지 않은 물병을 만들려고 한다.

물은 다음과 같이 재분배 한다.

먼저 같은 양의 물이 들어있는 물병 두 개를 고른다. 그 다음에 한 개의 물병에 다른 한 쪽에 있는 물을 모두 붓는다. 이 방법을 필요한 만큼 계속 한다.

이런 제약 때문에, N개로 K개를 넘지않는 비어있지 않은 물병을 만드는 것이 불가능할 수도 있다. 다행히도, 새로운 물병을 살 수 있다. 상점에서 사는 물병은 물이 1리터 들어있다.

예를 들어, N=3이고, K=1일 때를 보면, 물병 3개로 1개를 만드는 것이 불가능하다. 한 병을 또다른 병에 부으면, 2리터가 들어있는 물병 하나와, 1리터가 들어있는 물병 하나가 남는다. 만약 상점에서 한 개의 물병을 산다면, 2리터가 들어있는 물병 두 개를 만들 수 있고, 마지막으로 4리터가 들어있는 물병 한 개를 만들 수 있다.

입력

첫째 줄에 N과 K가 주어진다. N은 107보다 작거나 같은 자연수이고, K는 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 상점에서 사야하는 물병의 최솟값을 출력한다. 만약 정답이 없을 경우에는 -1을 출력한다.

알고리즘 분류

• 구현
• 그리디 알고리즘
• 시뮬레이션
• 비트마스킹

풀이

탐욕법(그리디 알고리즘)으로 분류되어 있는 문제는 규칙을 찾는 게 가장 중요하고, 시간을 많이 투자해야 한다.

다만 실제 코딩 테스트를 볼 땐, 알고리즘 분류를 알져주지 않기 때문에,

문제를 풀 때, 알고리즘 분류를 보지 않고 푸는 것을 권장한다.

 

우선 문제를 파악하고 규칙을 찾다보면, 어떠한 알고리즘을 사용해아 하는지 감이 온다.

특정 알고리즘이 떠오르지 않는다면 구현이나 탐욕법으로 구현해야할 것이다.

많은 문제를 풀어보고 다양한 알고리즘 유형에 대해 알고 있자.

 

우선 문제는 N개의 물이 1리터씩 들어있는 물병이 주어지고,

두 개의 같은 높이의 물병을 합쳐 총 물병의 개수를 K개 이하로 만들어야 하는 문제이다.

//N<=10^7, N>0

//K<=1000, K>0

규칙을 찾기 위해 N에 따른 각각의 경우들을 살펴보자.

N=1 {1}  //남은 물병의 개수 1

N=2 {1,1} -> {2} //남은 물병의 개수 1

N=3 {1,1,1} -> {2,1} //남은 물병의 개수 2

N=4 {1,1,1,1} -> {2,2} -> {4} //남은 물병의 개수 2

N=5 {1,1,1,1,1} -> {2,2,1} -> {4,1} //남은 물병의 개수 2

N=6 {1,1,1,1,1,1} -> {2,2,2} -> {4,2} //남은 물병의 개수 2

N=7 {1,1,1,1,1,1,1} -> {2,2,2,1} -> {4,2,1} //남은 물병의 개수 3

N=8 {1,1,1,1,1,1,1,1} -> {2,2,2,2} -> {4,4} -> {8} //남은 물병의 개수 1

N=12 {1,1,1,1,1,1,1,1,1,1,1,1} -> {2,2,2,2,2,2} -> {4,4,4} -> {8,4} //남은 물병의 개수 2

N=15 {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} -> {2,2,2,2,2,2,2,1} -> {4,4,4,2,1} -> {8,4,2,1} //남은 물병의 개수 4

N=16 {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} -> {2,2,2,2,2,2,2,2} -> {4,4,4,4} -> {8,8} -> {16} //남은 물병의 개수 1

 

N이 2의 x승일 때는 물병을 구매하지 않더라도 1개로 만들 수 있기 때문에 k값과 관계없이 항상 답은 0이다.

반대의 경우를 생각해보자.

 

N이 15일 때, 물병을 하나(answer) 더 구매한다면, N은 16이 되어 물병의 개수를 1로 만들 수 있다.

그러면 물병을 구매하지 않았을 때는(N==15) 물병을 몇 개로 줄일 수 있을까?

 

15개의 물병을 높이가 2인 물병으로 합치면 높이가 2인 물병 7개와 높이가 1인 물병 1개가 남는다. //{2,2,2,2,2,2,2,1}

 

남은 8개의 물병에서 높이가 2인 물병 7개를 높이가 4인 물병으로 합치면 높이가 1인 물병 1개, 높이가 2인 물병 1개가 남는다. //{4,4,4,2,1}

 

남은 5개의 물병에서 높이가 4인 물병을 높이가 8인 물병으로 합치면 높이가 8인 물병 1개, 높이가 4인 물병 1개, 높이가 2인 물병 1개, 높이가 1인 물병 1개로, 더 이상 물병을 합칠 수 없게 된다. //{8,4,2,1}

 

즉, K가 4(cnt)이상일 때는 물병을 구매하지 않아도 물병을 들어 옮길 수 있다.

 

따라서 N이 15일 때, K가 4(cnt)이상이면 물병을 구매하지 않아도 되고(answer=0),

k가 4(cnt)미만이면, 물병을 하나(answer=1) 구매해야 한다.

 

/*

처음엔 k의 값과 상관없이 n이 24라면 n보다 큰 2^x수인 36에서 24를 빼어서 answer=12를 구해서

k가 cnt미만이면 무조건 12를 출력하는 방법으로 접근하였으나,

k==cnt-1, k==cnt-2, ~~~, k==1일 때 각각 answer가 다른 경우가 있기 때문에 아래 코드와 같이,

k값에 따라 answer가 달라질 수 있게끔 코드를 짜줘야 한다.

*/

코드

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int n, k;
	cin >> n >> k;

	if (k >= n) {
		cout << 0;
	}
	else {
		int answer = 0;

		while (1) {
			int cnt = 0;
			int temp = n;
			while (temp > 0) {
				if (temp % 2 == 0) {
					temp /= 2;
				}
				else {
					temp /= 2;
					cnt++;
				}

			}
			//cnt가 k보다 작거나 같아지면 종료
			if (k >= cnt) {
				break;
			}

			n++;
			answer++;
		}
		cout << answer;
	}
	
	return 0;
}