[백준 14226] 이모티콘

문제

www.acmicpc.net/problem/14226

 

알고리즘

DP

 

풀이

$N$개의 이모티콘을 만들기 위해 사용하는 최소시간을 구하는 문제입니다.

 

$cache[i]$ = 이모티콘 $i$개를 만들기 위해 사용하는 최소시간

 

$i$상태에서 갱신할 수 있는 상태는 $i$의 배수상태들 입니다. $i$를 복사한후 계속 붙여넣기를 하면 계속 $i$의 배수들에 영향을 끼칠 수 있습니다. 또한 각 $i$때마다 모든 $j(2\leq j \leq 1000)$에 대하여 하나 빼준 $j-1$의 상태도 검사해주면 $O(N^2)$에 풀 수 있습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int cache[3000];

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    int N;
    cin >> N;
    fill(cache, cache + 3000, INT_MAX / 2);
    cache[1] = 0;
    for (int i = 1; i <= 1000; ++i) {
        for (int j = 2; j * i <= 1000; ++j) {
            cache[j * i] = min(cache[j * i], cache[i] + j);
        }
        for (int j = 1000; j >= 2; --j) {
            cache[j] = min(cache[j], cache[j + 1] + 1);
        }
    }
    cout << cache[N];
    return 0;
}