1050번 : 물약

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

1050번: 물약

N개의 주어진 재료와 M개의 조합식(또는 새로운 재료)를 갖고 LOVE를 만들 수 있는지 , 만들 수 있다면 그 최솟값은 무엇인지 구하는 문제이다.

 

아이디어 : 

우선, 주어진 재료들의 이름과 비용은 map을 사용해서 나타낼 수 있다.
조합식들은 항상 a=k1*m1+k2*m2+... 꼴로 나타낼 수 있으며 파싱을 잘 해서 {계수, 재료이름} 꼴로 나타낼 수 있다.

M제한이 50이고, 모든 식을 한번씩 돌면 하나의 식은 무조건 완성시킬 수 있다. (답이 안나오는 경우는 한 개의 식도 완성시킬 수 없으며, 이는 더이상 완성시킬 수 있는 식이 존재하지 않는다는 말이다.)
* 여기서 완성시킨다 라는 말은 조합식에서 필요한 재료들을 다 만들 수 있다는 말이다.
* a=1*b+2*c 라는 식이 있고, 주어진 재료로 b=1, c=2가 있으면 a=5로 식을 완성시킬 수 있다.

따라서 모든 식을 다 검색하는 것을 모든 식만큼 반복하면 M*M번만에 정답을 무조건 찾을 수 있다.

 

구현 : 

먼저 재료 문자열을 저장할 map이 필요하다. 한번이라도 등장한 문자열은 무조건 이 map에 속하게 된다.
문자열을 key로 두고, value는 최소 비용 또는 -1이 담기게 된다. -1은 재료를 만들 수 없음을 의미한다.

다음으로 식을 저장할 공간이 필요하다. 이차원 벡터로 선언했고, 각 공간마다 {계수, 재료이름}이 들어간다.
단, 벡터의 첫 공간에는 {0, 만들 재료}가 무조건 들어가게 된다.
선언은 vector<vector<pair<long long,string> > > ex(51); 으로 했다.

조합식의 파싱이 관건이다.

(만들 재료)=(재료1계수)(재료1)+(재료2계수)(재료2)..+(재료n계수)(재료n) 꼴로 주어지므로
처음 '='까지 string을 쌓아서 벡터의 첫 공간에 넣어주고, 그 다음 인덱스를 읽어서 계수로 저장해준 다음,
다음 '+' 또는 string이 끝날때까지 string을 쌓아서 벡터에 push_back({재료n계수, 재료n}) 해준다.
파싱 중에 새로운 문자열이 있으면 재료문자열 map에도 추가한다.

파싱이 끝나면 모든 식을 돌면서 식을 완성시킨다. 이 과정을 M번 더 반복 해주면 답을 찾을 수 있다.

 

코드 : 

#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
map<string, ll> m;
vector<vector<pair<ll,string> > > ex(51);
int main(){
	ios::sync_with_stdio(0); cin.tie(0);
	int N,M; cin>>N>>M;
	for(int i=0; i<N; ++i){
		string str; cin>>str;
		ll a; cin>>a;
		m[str]=a;
	}
	for(int i=0; i<M; ++i){
		string str; cin>>str;
		int idx=0;
		string s="";
		while(str[idx]!='='){
			s+=str[idx++];
		}
		ex[i].push_back({0,s});
		if(m.find(s)==m.end()){
			m[s]=-1;
		}
		while(1){
			string temp="";
			idx++;
			if(idx>=str.size()) break;
			ll coef=str[idx++]-'0';
			while(idx<str.size() && str[idx]!='+'){
				temp+=str[idx++];
			}
			ex[i].push_back({coef,temp});
			if(m.find(temp)==m.end()){
				m[temp]=-1;
			}
		}
	}
	for(int i=0; i<M; ++i){
		for(int j=0; j<M; ++j){
			ll cnt=0;
			string goal=ex[j][0].second;
			bool flag=true;
			for(int k=1; k<ex[j].size(); ++k){
				if(m[ex[j][k].second]==-1){
					flag=false;
					break;
				}
				cnt+=m[ex[j][k].second]*ex[j][k].first;
				if(cnt>1000000000) cnt=1000000001;
			}
			if(flag){
				if(m[goal]==-1) m[goal]=cnt;
				else m[goal]=min(m[goal],cnt);
			}
		}
	}
	if(m.find("LOVE")==m.end() || m["LOVE"]==-1){
		cout << "-1\n";
	}
	else{
		cout << m["LOVE"] << '\n';
	}
}