BOJ)14226 이모티콘

문제: icpc.me/14226

이모티콘에 대한 연산이 주어질 때 이모티콘 S개를 치기 위해 필요한 시간의 최솟값을 구하는 문제이다.

화면에 존재하는 이모티콘을 복사해서 붙여넣는 경우는 2의 시간이 이모티콘 하나를 삭제하는 경우는 1의 시간이 걸린다 생각하고 다익스트라를 돌렸는데 WA를 계속 받았다.

문제 조건을 잘 확인해보니 한번 복사한 이모티콘을 여러번 붙여넣을 수 있는 것같았다.

그래서 다익스트라에서 pq의 3번째 인자로 붙여넣었을 경우의 붙여넣은 수를 인자로 주어 붙여넣기 하였을 경우 다시 붙여넣을 수 있게 소스를 수정하여 맞았다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
int dp[2010], s;
int main() {
    memset(dp, -1, sizeof(dp));
    scanf("%d", &s);
    priority_queue<pair<int, pair<int, int>>> pq;
    pq.push({ 0,{1,0} });
    while (pq.size()) {
        int here = pq.top().second.first;
        int cost = -pq.top().first;
        int b = pq.top().second.second;
        pq.pop();
        if (b)
            if (0 < here + b&&here + b < 2010)
                pq.push({ -cost - 1,{ here + b,b } });
        if (dp[here] != -1)continue;
        dp[here] = cost;
        if (s == here)break;
        if (0 < here - 1 && here - 1 < 2010 && dp[here - 1] == -1)
            pq.push({ -cost - 1,{ here - 1 ,0 } });
        if (0 < 2 * here && 2 * here < 2010 && dp[2 * here] == -1)
            pq.push({ -cost - 2,{ 2 * here,here } });
    }
    printf("%d\n", dp[s]);
    return 0;
}