boj 14226 이모티콘

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

14226번: 이모티콘

우선 입력되어있는 이모티콘 1개를 복사해서 계속 붙여나가는 시간을 계산하였습니다.

(dp[1]=0이지만 입력에 1이 주어지지 않기때문에 1로 하였습니다.)

그 다음은 클립보드에 이모티콘을 하나씩 늘려가면서 현재의 클립보드로 계속 이어나갈 경우,

현재의 클립보드로 이어나간 후 하나씩 삭제할 경우를 고려하여 계산하였습니다.

 

 

#include <iostream>
#include <algorithm>
using namespace std;
 
int dp[2001], clip;
 
int func(int N) {
    dp[1] = 1;
    for (int i = 1; i <= 2000; i ++) {
        dp[i + 1] = dp[i] + 1;
    }
    
    clip = 2;
    while (clip <= 1001) {
        int r = dp[clip] + 2;
        dp[clip * 2] = min(dp[clip * 2], dp[clip] + 2);
        for (int i = clip * 3; i + clip <= 2000; i += clip) {
            dp[i] = min(dp[i], r + 1);
            r++;
        }
 
        for (int i = clip * 2 - 1; i >= clip + 1; i--) {
            dp[i] = min(dp[i], dp[i + 1] + 1);
        }
        clip++;
    }
 
    return dp[N];
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    int N;
    cin >> N;
    cout << func(N) << '\n';
 
    return 0;
}