[platinum4] [해설, 분류 미확인]boj9446 아이템 제작

 

 

 

 

 

재밌는 다익스트라 활용 문제였다.

다익스트라의 그리디한 성질을 잘 활용하면 아이디어를 떠올리기 어렵지 않을 것이다.

아이템 조합은 두가지를 조합해 한개를 만드는 것인데,  아이템1 + 아이템2 = 아이템3

이라면 아이템3 가격은 아이템1가격 + 아이템2 가격 인 셈이 될 것이다.

그리디하게 접근하자면, 우선 각 아이템마다 원래의 아이템 가격이 있고, 이제 그 아이템들 끼리 조합해 만든 아이템의 가격중 최소를 구한다.

즉 우선순위큐에 아이템들을 합친값이 원래 가격보다 작다면, 새로운 아이템을 넣는다.

그렇게 아이템들을 우선순위큐에 넣은후, 

우선순위큐에서 poll 하면  그게 새로 업데이트된 아이템 가격중 최소의 가격이 될 것이다.

 

다음과 같이  큐에서 poll한 값이 1번이면,  1번이 지금 합성할 수 있는 아이템 중에 비용합이 최소임이 확정되는 것이다. 그럼 이제   1번을 재료로 하는 4번 , 5번도 새로 업데이트해 우선순위큐에 넣어야 한다.

그런데 이제 불안요소가 있다. 4번 , 5번을 큐에 넣긴 할텐데, 재료가 되는 2번, 3번은  업데이트가 되지 않았는데 그냥 넣어도 되는가? 이다.  그러나 걱정할 필요 없다. 2번이 업데이트되면 2번을 재료로 하는 4번도 새로 업데이트해 우선순위큐에 넣을 것이고, 3번 업데이트시 업데이트된 5번을 새로 넣을 것이기 때문.

 

그럼 또 한가지 불안요소가 발생한다. 만약 1번 + 2번 합쳐 4번을 큐에 넣었는데,   다음에 poll한 값이 4번이라면? 아직 2번은 채 업데이트도 못했는데?  그것도 걱정할 필요 없다. 4번을 뽑았을 때는 합성아이템중 4번 비용이 최소라는 뜻인데,  2번이 아직 업데이트가 안됬다는 것은 4번비용보다 크다는 뜻이 된다.따라서 나중에 2번을 업데이트 한다 한들 1번과 새로 업데이트 된 2번을 합성하면 현재 뽑은 4번보다 값이 커질 것이므로, 말이 안된다.

 

뇌절이지만 그럼 또 하나의 불안. 그럼 한가지 아이템이 업데이트될 때마다,  새로 합성되는 아이템들을 모두 업데이트해 큐에 넣어야 하는데, 메모리 시간 초과가 나지 않을까? 

 사실 이부분으로 좀 헷갈렸는데,    그렇지 않다.

우선순위큐에서 n을 뽑을 때마다 n의 최솟값이 확정된 상태이므로, 이때 n이 재료가 되는 아이템을 모두 업데이트 후큐에 넣는다.

그러나 모든 n은 한번 씩만 업데이트 된다. 위에서 1번이 업데이트 되면 , 4,5번을 업데이트, 2번이 업데이트 되면 4번 업데이트, 3번이 업데이트 되면 5번을 업데이트 한다. 

즉 큐에 넣는 횟수는 간선의 수(2*N)만큼이다. 따라서 시간,메모리 초과는 걱정 할 필요 없다.

 

정리하면 이렇다.

1.dp에 우선 각 아이템의 원래가격을 넣는다.

2.각 아이템 합성된 값이 원래가격보다 작다면, pq(우선순위큐)에 넣는다.

3. 우선순위큐를 poll하면서, poll한 값을 재료로 하는 아이템들 가격을 새로 업데이트하고  pq에 넣는다. 당연히 업데이트 된 가격이 기존 dp값보다 크거나 같으면 넣지 않는다.

4. 이렇게 다익스트라를 종료한 후 dp[1]값 출력