[BOJ 2281]데스노트

[BOJ 2281]데스노트

이 문제는 두 가지 방법으로 풀었는데 내가 처음으로 풀었던 방법은 시간이 더 오래 걸렸다. 그래서 시간이 짧은 다른 풀이로 한번 더 풀었다. 두 풀이 모두 dp를 기초로 하는 풀이기는 하지만 dp테이블의 의미가 달랐다. 내가 처음으로 푼 방식은 구간별로 길이의 합과 그 합을 m에서 뺀 값의 제곱을 미리 다 구해놓았다. 그 값들을 바탕으로 3중 for문을 돌았기 때문에 시간 복잡도는 거의 O(N^3)이라고 할 수 있다. N=1000이기 때문에 거의 터질 수도 있는 풀이지만 온전히 N^3을 도는 것은 아니라서 시간 안에 들어온 것 같다. 이 풀이의 경우 dp[a][b]=c의 의미는 'a부터 b번 째 이름 전까지(표기상으로 '[a,b)')의 합으로 만들 수 있는 최소 공백의 제곱의 합(=c)'이다. 이 풀이의 경우 316ms를 받았다.(1초 제한)

#include<stdio.h>
#include<algorithm>
using namespace std;
#define SIZE 1009
#define INF (1<<30)-1
int dp[SIZE][SIZE],sum[SIZE][SIZE];
int arr[SIZE],p_sum[SIZE];
int main(){
    int n,m;    scanf("%d %d",&n,&m);
 
    for(int i=1 ; i<=n ; i++){
        scanf("%d",&arr[i]);
        p_sum[i]=p_sum[i-1]+arr[i];
    }
 
    for(int i=1 ; i<=n+1 ; i++){
        for(int j=1 ; j<=n+1 ; j++){
            dp[i][j]=INF;
        }
    }
 
    for(int i=1 ; i<=n+1 ; i++){
        for(int j=i ; j<=n+1 ; j++){
            if(i==j){
                sum[i][i]=0; continue;
            }
            sum[i][j]=p_sum[j-1]-p_sum[i-1];
            sum[i][j]+=(j-i-1);
 
            if(sum[i][j]<=m) //
                dp[i][j]=(m-sum[i][j])*(m-sum[i][j]);
            else dp[i][j]=INF; //
        }
    }
 
    for(int i=1 ; i<=n ; i++){
        for(int j=1;  j+i<=n+1 ; j++){
            for(int k= j ; k<=j+i ; k++){
                dp[j][j+i]=min(dp[j][j+i],dp[j][k]+dp[k][j+i]);
            }
        }
    }
 
    int ans=1<<30;
    for(int i=n ; i>=1 ; i--){
        if(sum[i][n+1]<=m){
            ans=min(ans,dp[1][i]);
        }
    }
    printf("%d\n",ans);
 
    return 0;
}

두 번째 풀이는 재귀함수를 이용한 탑다운 dp이다. 이 풀이의 경우 dp[a][b]=c의 의미는 '현재 b번째 글자를 데스노트 어느 줄의 a번째 칸까지 쓸 때, 남은 글자를 모두 써넣기 위해서 필요한 최소 공백의 제곱의 수'이다. 내가 현재 써야할 이름을 현재 줄에 이어서 쓰는 경우도 있을 수 있고, 다음 줄에 새롭게 쓰는 경우가 있다. 다만 이어서 쓰려면은 반드시 남아 있는 공백의 수가 쓰려는 글자 수보다 크거나 같아야 한다는 조건이 필요하다. 이 풀이의 경우 4ms가 나왔다.

#include<stdio.h>
#include<algorithm>
using namespace std;
#define SIZE 1009
int n,m;
int dp[SIZE][SIZE],arr[SIZE];    
int rec(int pos,int cnt){
    if(cnt==n) return 0;
 
    int &ret=dp[pos][cnt];
    if(ret!=-1) return ret;
 
    ret=rec(arr[cnt]+1,cnt+1)+(m-pos+1)*(m-pos+1); //다음 줄에 새롭게 씀
    if(pos+arr[cnt]<=m)  //현재 줄에 이어서 씀
        ret=min(ret,rec(pos+arr[cnt]+1,cnt+1));
 
    return ret;
}
int main(){
    scanf("%d %d",&n,&m);
 
    for(int i=0 ; i< n ; i++)
        scanf("%d",&arr[i]);
 
    for(int i=0 ; i<SIZE ; i++){
        for(int j=0 ; j<SIZE ; j++)
            dp[i][j]=-1;
    }
 
    int ans=rec(arr[0]+1,0+1);
    printf("%d\n",ans);
 
    return 0;
}