[백준 1050] 물약

1050번: 물약 (acmicpc.net)

 

알아야 하는 것

STL : map, min(int, int)

이 것만 알아도 풀 수 있다.

생각해야할 것

이 문제는 생각할 것들이 많은 문제였다.

그에 대한 질문을 모아놓았길래 이를 토대로 한번 포스팅 해볼려고 한다.

글 읽기 - 1050 포션 문제를 풀던 도중 경우의 수에 대해 질문드립니다. (acmicpc.net)

글 읽기 - 1050 포션 문제를 풀던 도중 경우의 수에 대해 질문드립니다.

나는 이 질문에서 4, 5번 이 생각할 만한 것 같은 것 같다.(나머지는 고려하지 문제 푸는데 의미는 없을 듯/ 괜한 걱정)

 

1.판매도 하고 조합도 되는데 조합 단가가 더 싼 품목

A=10  B=1

A=1B   ----> A=min(A, B*1)

일때 이 조건은 성립 된다. 이럴 때는 A의 단가를 최신화 시키면 된다.

 

2. 포션이 상호간 재료로 포함되는 경우

A=1B   B=1A

일때는 A의 단가를 알고 있을때만 B=1A 연산을 실행하면 된다.

 

힌트

이러한 생각들도 중요하긴 한데 m의 범위가 이 문제의 힌트라고 말할 수 있다.

m<=50이니 많이 계산을 해도 시간은 괜찮을 것 같았다.

 

아이디어

이 문제에서는 단가들의 최신화이다.

1. 조합이 가능하면 조합후 단가를 최신화

2. 과정 1을 m번 반복

3. 과정 2을 m번 반복

이러면 꼼꼼하게 최신화가 되니 답이 나올 것이고, O(m^2)의 시간 복잡도를 갖게 되니 시간제한에도 걸리지 않을 것이다.

 

코드(C++)

#include <bits/stdc++.h>
using namespace std;
string c[100]; bool f2[100];
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    map<string, long long int> A;
    int n, m; cin>>n>>m;

    for(int i=0; i<n; i++)
    {
        string a; int b;
        cin>>a>>b; A[a]=b;
    }

    vector<pair<string, int> > M[100];

    for(int i=0; i<m; i++)
    {
        string a, b="";
        cin>>a; int d=0; a+="+";

        for(int j=0; j<a.length(); j++)
        {
            if(a[j]=='=')
            {
                c[i]=b;
                b="";
            }
            else if(a[j]=='+')
            {
                M[i].push_back({b, d});
                b=""; d=0;
            }
            else if(0<a[j]-'0' && a[j]-'0'<10)
            {
                d=a[j]-'0';
            }
            else
            {
                b+=a[j];
            }
        }
    }

    for(int i=0; i<m; i++)
    {
        for(int i=0; i<m; i++)
        {
            bool f=0;
            for(int i=0; i<m && !f; i++)
            {
                long long int p=0; bool F=0;
                if(f2[i]) continue;
                for(int j=0; j<M[i].size() && !F; j++)
                {
                    string a; int b;
                    a=M[i][j].first;
                    b=M[i][j].second;

                    if(!A[a]) F=1;
                    else p+=A[a]*b;
                    if(p>1000000000) p=1000000001;
                }

                if(!F)
                {
                    if(A[c[i]]==0) A[c[i]]=p;
                    A[c[i]]=min(p, A[c[i]]); f=1; f2[i]=1;
                }
            }

            if(!f) break;
        }

        for(int i=0; i<m; i++) f2[i]=0;
    }

    string a="LOVE";
    if(A[a]>1000000000) A[a]=1000000001;
    if(!A[a]) cout<<-1;
    else cout<<A[a];

    return 0;
}