[BOJ/백준][Gold5] 2228 : 구간 나누기 (C++)

 

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

2228번: 구간 나누기

 

 

[난이도] Gold5
[유형] DP

[풀이]
DP[n][m] : n번째 원소부터 선택이 가능하고 현재까지 총 m개의 구간을 구했을 때, 만들 수 있는 최댓값

부분합을 미리 구해놓는다 -> sum[i][j] : i~j까지의 합.

Top-Down 방식으로 풀었다. sol(n,m) 은 DP[n][m]

점화식 :
1) n번째 원소를 어느구간에도 포함시키지 않는 경우
=> sol(n,m) = sol(n+1,m) (구간은 증가하지 않고 n만 1 증가)

2) n번째 원소를 첫번째 원소로 해서 만들 수 있는 모든 구간을 구해보는 경우
=> sol(n,m) = max(sum[n][i]+sol(i+2,m+1)) ( n <= i < N )

1,2의 최댓값이 정답이다.

종료조건 :
m==M 인 경우 => 모든 구간을 다 찾았으므로 0을 return
m=N인 경우 => 새로운 구간을 만들 수 없으므로 음의 무한대 -9e8을 return

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,a[100],dp[100][51],sum[100][100],inf=9e8;
int sol(int n,int m){
    if(m==M) return 0;
    if(n>=N) return -inf;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret=sol(n+1,m);
    for(int i=n;i<N;i++){
        ret=max(ret,sum[n][i]+sol(i+2,m+1));
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<N;i++){
        int s = 0;
        for(int j=i;j<N;j++){
            s+=a[j];
            sum[i][j]=s;
        }
    }
    printf("%d",sol(0,0));
}

 

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/2228.cpp