BOJ 9446 - 아이템 제작

문제 링크 : https://www.acmicpc.net/problem/9446

문제 태그

DP,정렬

문제 소개

모든 물건을 각 가격에 살 수 있다. 하지만, 조합식에 따라서 두 물건을 합쳐 새로운 물건을 만들 수도 있다. 이때 1번물건을 만들기 위해서 필요한 최소가격을 구하자. 

문제 풀이

문제를 보고 DP가 생각이 났다.
DP table 정의도 바로 DP[i]=i번째 물건을 얻는 데 필요한 최소 비용. 
또한 식은 i,j로 k를 만들 때 $DP[k]=min(DP[k],DP[i]+DP[j])$로 업데이트를 할 수 있다. 

여기서 DP의 필요조건을 생각해보자. 어떤 DP table을 채울 때 사용되어진 값들이 있다면 그 사용되어진 값들은 확정된 상태여야 한다. 즉, 위의 식으로 따지면 DP[k]의 최종값을 만드는 i,j는 더이상 변하지 않는 확정 값이어야 한다. 
따라서 for문을 통해서 1번 물건 부터 순서대로 DP값을 정할 수는 없고, 새로운 방식과 기준을 통해서 순서대로 DP값을 정의해야 한다. 

조건을 활용하자! 모든 구매가격은 음이 아닌 정수이기 때문에 k가 i와 j로 만드는 것이 최종이라고 하면 $DP[i] \leq DP[k]$ , $DP[j] \leq DP[k]$ 이다. 따라서 k를 완벽히 정의하기 전에 i j를 정의 하는 방법은 DP 값이 가장 작은 순서대로 하면 된다. 

하지만 DP값의 최종값이 어떻게 될 줄 알고 순서를 정할 수 있을까. DP의 업데이트 시점을 바꾸면 이 문제를 해결이 가능하다. 즉 k를 만들 수 있는 i,j 로 k를 업데이트 하는 것이 아니라 i,j가 둘 다 확정된 시점에서 k를 업데이트 시켜주는 것이다. 그러면서 pq를 관리하면서 다음으로 값을 확정시킬 물건을 찾아내면 된다.

따라서 이 문제의 풀이에 대한 전체로직은 다음과 같다.
1. 값 - 물건을 pair를 취해서 pq에 넣는다. 이때 맨 처음에는 구매가격에 대해서 넣는다.
2. pq의 가장 위에서 빼면서 아직 값이 확정되지 않은 물건을 뽑아낸다. 그 물건에 대한 값을 pq에서 뽑은 pair의 값으로 확정을 지어준다.
3. 방금 확정시켜준 물건 i에 대해서 이미 확정된 물건들 j에 대해서  i,j 가 k를 만든다면  $DP[k]=min(DP[k],DP[i]+DP[j])$로 업데이트를 시켜준다.
4. 이때 최솟값이 바뀌었다면 그 값과 물건을 pair로 취해서 pq에 넣는다.
5. 모든 물건에 대한 값을 확정시킬때 까지 위의 과정을 반복한다.

코드

#include<bits/stdc++.h>
using namespace std;
typedef int ll;
typedef pair<ll,ll> pii;
 
#define ff first
#define ss second
#define ep emplace_back
#define eb emplace
#define pb push_back
 
ll arr[1010101];
ll vis[1010101];
priority_queue<pii,vector<pii>,greater<pii>> pq;
vector<pii> v[10101];
 
 
 
 
int main(){
    ll i,j,k,l,m,n;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        pq.push({arr[i],i});
    }
 
    for(i=1;i<=m;i++){
        ll a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        v[b].pb({c,a});
        v[c].pb({b,a});
    }
 
    while(!pq.empty()){
        ll x=pq.top().ss; pq.pop();
        if(vis[x]) continue;
        //printf("%d %d\n",x,arr[x]);
        for(auto k:v[x]){
            if(vis[k.ff]&&arr[k.ss]>arr[k.ff]+arr[x]){
                arr[k.ss]=arr[k.ff]+arr[x];
                pq.push({arr[k.ss],k.ss});
            }
        }
        vis[x]=1;
    }
 
    printf("%d",arr[1]);
}