BOJ 14226 이모티콘

www.acmicpc.net/problem/14226

14226번: 이모티콘

 

해당 문제를 점화식으로 바꿀 수 있다.

arr[ i*j ] = min ( arr[ i*j], arr[ i ] + j  ) , j >=2   <- 복사를 사용한 경우

arr[ i ] = min ( arr[ j ] , arr[ i + 1 ] ) <- 삭제의 경우

점화식이 세워졌으니 DP라고 확신하였고, 해당 방법으로 문제를 풀었다.

 

사실 문제를 3달 전에 처음 봤지만, 이제야 정답을 맞았다.

 

내가 계속 틀렸던 이유는, 이모티콘 삭제 시간 탐색을 정방향으로 했기 때문이다.

이모티콘 삭제를 통해 i개의 이모티콘을 만드는 경우, i개 보다 큰 이모티콘을 만드는 시간에 영향을 받는데, 복사를 통해 이모티콘을 만드는 방법으로 인해 i보다 큰 이모티콘을 만드는 시간이 계속 갱신되기 때문에, 삭제를 이용한 최단 시간도 계속 갱신해주어야한다.

위와 같은 생각으로 코드를 수정하였고, 정답을 받을 수 있었다.

 

아래는 제출 코드이다.

#include <cstdio>
#define min(a, b) (((a) < (b)) ? (a) : (b))
int DP[2001];



int main(){

    int s; scanf("%d",&s);
    DP[1] = 0;
    for(int i=2;i<=2000;i++) DP[i] = i;
                           
    for(int i=2;i<=2000;i++){
        for(int j=2;j*i<=2000;j++){
            DP[i*j] = min(DP[i*j], DP[i]+j);
        }
        /*
        수정 전
        for(int j=1;i-j>=2;j++)
            DP[i-j] = min(DP[i-j], DP[i]+j);
        
        */
       for(int j = 1999; j > i; j--){
            DP[j] = min(DP[j], DP[j+1] + 1);
       }
    }
    DP[1] = 0;


    printf("%d\n",DP[s]);


    return 0;
}