[BOJ] 구간 나누기 - Compy's Blog

구간 나누기

TimeLimit	MemoryLimit	Condition	TAG
1s	128MB	(1 <= N <= 100, 1<=M<=[N/2] -32768 <= num <= 32767 )	DynamicProgramming(DP)

N(1 ≤ N ≤ 100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1 ≤ M ≤ ⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 한다.
각 구간은 한 개 이상의 연속된 수들로 이루어진다.
서로 다른 두 구간끼리 겹쳐있거나 인접해 있어서는 안 된다.
정확히 M개의 구간이 있어야 한다. M개 미만이어서는 안 된다.
N개의 수들이 주어졌을 때, 답을 구하는 프로그램을 작성하시오.

문제를 처음 보고서 바로 dp로 접근한 나에게 칭찬 드립니다!

문제를 보자마자 dp에 대한 정의를 했습니다. 이후 이 dp 식에 맞도록 bottom-up으로 문제를 풀이하였습니다.

저의 아이디어는 dp[i][j]는 현재 수열에서 i번째를 보고 있을 때, j번째의 구간이다. 그렇기에 i는 N보다 작으며, j는 m보다 작다.

이렇게 다 구한 후 m개의 구간으로 나눠진 조합 중 제일 큰 것들을 업데이트하고 최종적으로 제일 큰 값을 고르면 최적해를 찾을 수 있다.

정답 코드

#include <iostream>

using namespace std;

const int pre = -2100000000;

int n, m;
int nums[101];
int dp[101][101];
int main(){
    // dp[i][j][k]는 i번째 일때, j개의 연속된 값에서 k번째의 구간이다. 라는 의미이다.
    // 다시 정의한다. dp[i][j]는 i 번째 일때, j번째의 구간이다.
    
    cin >> n >> m;
    
    for(int i = 0; i < n; i ++) cin >> nums[i];
    
    if(m == 1) {
        int mymax = pre;
        for(int i = 0; i < n; i++) mymax = max(mymax, nums[i]);
        cout<< mymax;
        return 0;
    }
    
    for(int i = 0; i < n+1; i++)
        for(int j = 0; j < n+1; j++) dp[i][j] = pre;
    
    dp[0][0] = nums[0];
    for(int i = 1; i < n; i ++){
        dp[i][0] = max(dp[i-1][0]+nums[i], nums[i]);
        for(int j = 1; j < m+1; j++) dp[i][j] = max(dp[i][j], dp[i-1][j] + nums[i]);
        for(int j = 0; j < i-1; j++){
            for(int k = 1; k < m+1; k++) dp[i][k]=max(dp[i][k], dp[j][k-1]+nums[i]);
        }
    }
    
    int result = pre;
    for(int i = 0; i < n+1; i++) result = max(dp[i][m-1], result);
    
    
    cout << result;
    return 0;
}