[백준 알고리즘] 1050번 물약 c++

각 재료의 비용을 map구조를 이용해 'cost[재료명] = 비용'이 되도록 저장하였다.

m개의 식이 주어질 때, find함수를 활용하여 처음은 구분자 '=' 이후에는 구분자 '+'로 문자열을 파싱하였다.

처음보는 재료명이 나오면 cost[재료명] = -1로 저장하였고,

벡터v에 식에 대한 내용을 S와 벡터 _v(n1 s1, n2 s2....)형식으로 저장하였다.

 

vector<pair<string, vector<pair<int, string>>>> v

v[i].first = S, v[i].second = ({n1, s2}, {n2, s2}....)

 

입력을 다 받고 나면 물약의 식을 저장한 v벡터를 탐색 함으로 결과를 구할 수 있다.

i for문 : 0~v.size() 모든 물약의 식 탐색

j for문 : 0~v[i].second.size() Nj * Sj  값을 sum값에 더해줌.

이때 Sj의 비용이 구해지기 전(cost[Sj]가 -1)이라면 sum = -1 후 break 

 

j for문을 다 돌았을 때, sum이 -1이 아니고 cost[S]가 -1이거나 cost[S]>sum일 경우,

cost[S] = sum을 저장하고, flag를 true로 만들어 i for문을 다시 탐색하게 한다.

 

flag로 모든 물약의 식을 탐색했을 때, 비용이 구해지거나 바뀐 물약이 있으면

다시 모든 물약의 식을 탐색할 수 있게 하여

모든 경우에서 LOVE의 최솟값을 탐색할 수 있다.

 

최종 결과는 cost["LOVE"] 값을 확인하면 구할 수 있다.

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

int main(){
	const int limit = 1000000000;
	int n, m;
	

	cin >> n >> m;

	vector<pair<string, vector<pair<int, string>>>> v;
	map<string, int> cost;

	string s1,s2;
	int c1;
	for(int i=0; i<n; i++){
		cin >> s1 >> c1;
		cost[s1] = c1;
	}

	for(int i=0; i<m; i++){
		string tmp = "";
		cin >> tmp;

		size_t prev =0 , cur;

		cur = tmp.find('=');
		s1 = tmp.substr(prev, cur-prev);
		prev = cur+1;

		vector<pair<int, string>> _v;
		while(1){
			cur = tmp.find('+', prev);
			if(cur == string::npos)
				cur = tmp.size();
			s2 = tmp.substr(prev, cur-prev);
			c1= s2[0] - '0';
			s2 = s2.substr(1);
			prev = cur+1;

			if(cost.find(s2) == cost.end()){
				cost[s2] = -1;	
			}
			_v.push_back(make_pair(c1,s2));

			if(cur == tmp.size())
					break;
		}
			
		if(cost.find(s1) == cost.end()){
			cost[s1] = -1;
		}
		v.push_back(make_pair(s1,_v));
	}

	bool flag =true;
	while(flag){
		flag = false;
		for(int i=0; i<v.size(); i++){
			long long sum = 0;
			string name = v[i].first;
			for(int j=0; j<v[i].second.size(); j++){
				int cnt = v[i].second[j].first;
				string x = v[i].second[j].second;
				if(cost[x] != -1){
					sum += cnt * (long long)cost[x];
					if(sum > limit)
						sum = limit + 1;
				}
				else{
					sum = -1;
					break;
				}
			}
			if(sum > 0){
				if(cost[name] == -1 || cost[name] > sum){
					cost[name] = sum;
					flag =true;
				}
			}
		}
	}

	if(cost.find("LOVE") == cost.end())
		cout << "-1" << endl;
	else
		cout << cost["LOVE"] << endl;

	return 0;
}