[백준 11964] Fruit Feast (C++)

문제 링크: www.acmicpc.net/problem/11964

11964번: Fruit Feast

1. 주의할 점

- 그리디로 접근하지 않도록 한다(예외를 잘 처리하면 가능할지도..?. Ex. 9 5 6)

 

2. 구현

- BFS를 통해 구현한다

- Check[] 배열을 모두 초기화하며, 해당 숫자에 도달할 수 있으면 True를 가진다

- Queue에는 현재 숫자와 물을 마셨는지에 대한 여부를 나타내는 변수를 담는다

- A와 B가 숫자가 같을 수 있으므로, 벡터를 통해 구분한다(같다면 중복연산을 더 하지 않도록)

- BFS를 통해 다음 숫자가 T보다 작고 방문한적이 없다면 방문 혹은 아직 물을 안마셨고, 현재 값의 반 + 벡터의 숫자(A or B)가 T보다 작고 방문한 적이 없다면 방문한다. 위의 2가지 중 1개를 만족할 경우, Result를 항상 갱신한다

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
struct info {
	int val;
	bool half;
};
info tmp;
bool check[5000001] = { false, };
vector<int> v;

int main() {
	int t, a, b, result;
	cin >> t >> a >> b;
	result = a;
	queue<info> q;
	tmp.half = false;
	tmp.val = a;
	check[a] = true;
	q.push(tmp);
	v.push_back(a);
	if (!check[b]) {
		tmp.val = b;
		check[b] = true;
		q.push(tmp);
		result = max(result, b);
		v.push_back(b);
	}

	while (!q.empty()) {
		int cv = q.front().val;
		bool ch = q.front().half;
		q.pop();
		for (int i = 0; i < v.size(); i++) {
			int nv = v[i] + cv;
			if (nv <= t && !check[nv]) {
				result = max(result, nv);
				check[nv] = true;
				tmp.half = ch;
				tmp.val = nv;
				q.push(tmp);
			}
			if (!ch) {
				nv = cv / 2 + v[i];
				if (nv <= t && !check[nv]) {
					result = max(result, nv);
					check[nv] = true;
					tmp.half = true;
					tmp.val = nv;
					q.push(tmp);
				}
			}
		}
	}
	cout << result;
	return 0;
}