백준 14226번 - 이모티콘

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

14226번: 이모티콘

필요한 배경지식

• 다익스트라 or BFS
• DP

 

문제 해결 방법

이모티콘 N개를 만들기 위한 시간의 최소값을 출력하기 위해 다음과 같은 DP배열을 사용했습니다.

 

dp[N][C] = 현재 이모티콘이 N개이고 클립보드에 저장된 이모티콘의 개수가 C개 일때, 필요한 시간의 최솟값

 

이렇게 정의하면 3가지 연산에 대하여 다음과 같은 식이 성립합니다.

현재 이모티콘의 개수가 n, 클립보드에 복사된 이모티콘의 개수가 c 라면

1. 복사 연산       : dp[n][n] = dp[n][c] + 1
2. 붙여넣기 연산 : dp[n+c][c] = dp[n][c] + 1
3. 삭제 연산       : dp[n-1][c] = dp[n][c] + 1

 

저는 문제를 풀때, 삭제가 들어간 연산때문에 첫번째 방문한 값이 최적의 해가 아닐수도 있다고 생각해서 다익스트라를 이용했는데 다른 사람들의 코드를 확인해 보니 위처럼 dp배열을 정의할 경우 단순 BFS로도 풀리는것 같습니다.

 

아래의 제 코드는 다익스트라를 사용한 코드이며 제 코드에서

dp배열을 단순히 방문처리만 하는 배열로 사용하여 BFS로 풀어내면 더 빠른 시간안에 문제를 해결할 수 있습니다.

 

 

 

전체코드

#include<bits/stdc++.h>
#define xx first
#define yy second
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using tpi = tuple<int,int,int>;
using tpl = tuple<ll,ll,ll>;
using dpi = pair<pii,pii>;
using dpl = pair<pll,pll>;
const int INF = 0x3f3f3f3f;

int N;
int dp[1005][1005]{};

void bfs(){
    memset(dp,0x3f,sizeof(dp));
    priority_queue<tpi, vector<tpi>, greater<tpi>> pq;
    pq.push({0,1,0});
    dp[1][0] = 0;

    while(!pq.empty()){
        int d,n,c;
        tie(d,n,c) = pq.top();
        pq.pop();
        
        if(dp[n][c] < d) continue;
        if(dp[n][n] > d+1){
            pq.push({d+1,n,n});
            dp[n][n] = d+1;
        }
        
        if(n+c < N+2 && dp[n+c][c] > d+1){
            pq.push({d+1,n+c,c});
            dp[n+c][c] = d+1;
        }

        if(n-1 > 0 && dp[n-1][c] > d+1){
            pq.push({d+1,n-1,c});
            dp[n-1][c] = d+1;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>N;
    
    bfs();

    int res = INF;
    for(int i=0; i<N+2; i++){
        res = min(res, dp[N][i]);
    }
    cout<<res;
}