[5032] 탄산 음료 C++

5032. 탄산음료

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

5032번: 탄산 음료

 

반 병의 수 e, 그날 발견한 빈 병의 수 f, 새 병으로 바꾸는데 필요한 빈 병의 개수 c가 주어진다. 이를 활용해서 먹을 수 있는 탄산음료의 개수를 출력해야한다.

 

첫번째 예제 입력을 살펴보자. 입력은 9 0 3이고 출력은 4이다. 

많은 사람들이 여기서 많은 고민을 했을거 같다.

"처음에 9병이 있었고 0병을 발견했으면 바꿀 수 있는 병은 총 9/3=3 병 아닐까?"

필자는 위와 같은 고민에서 헤어나오지 못 했다...... 대체 왜 출력이 4병일까... 오랜 고민 끝에 이유를 찾아냈다.

바로 새로 얻은 3병을 통하여 또 다른 1병의 음료를 받을 수 있다.

때문에 우리가 고려해야하는 것은 기존의 병으로 바꿀 수 있는 음료의 수 + 새로운 병으로 바꿀 수 있는 음료의 수이다.

 

필자는 new_b 변수를 선언하여 새로운 병의 수를 저장하였다. 그리고 새로운 병의 수를 벡터(n_b)에 저장했다. 

벡터는 트레이드로 생긴 병의 수를 저장하는 곳이다. 그리고 첫번째 트레이드를 끝내고 남아있는 병이 있을 수 있기 때문에 이 역시 고려해야한다. 

 

만일, 첫번째 트레이드 이후 남아있는 병이 있다면 새로 얻은 병과 더해준다. 그리고 이 값이 만일 트레이드할 때 필요한 병의 수보다 크다면 다시 한번 위의 과정을 반복한다. (재귀방식으로 구현)

int new_b;
vector<int> n_b;
void solve(int b) {
	
	new_b = b / c;
	n_b.push_back(new_b);
	new_b += b % c;
	if (new_b >= c) {
		return solve(new_b);
	
	}
	
	

}

 

마지막으로는 벡터에 저장된 새로 얻은 병들의 합을 sum이라는 변수에 모두 더하여 결과값을 얻었다.

 

코드:

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int e, f, c;
int sum;
int new_b;
vector<int> n_b;
void solve(int b) {
	
	new_b = b / c;
	n_b.push_back(new_b);
	new_b += b % c;
	if (new_b >= c) {
		return solve(new_b);
	
	}
	
	

}

int main() {
	ios::sync_with_stdio(0);
	cout.tie(); cin.tie();
	
		
	cin >> e >> f >> c;
	
	solve(e+f);
	
	for (int i = 0; i < n_b.size(); i++) {
		sum += n_b[i];
	}

	cout << sum;
}