[1일 1알고] G5 16494 가장 큰 값

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

 

dp혹은 브루트포스를 사용해 풀 수 있는 문제입니다.

 

개인적으로는 dp를 생각하고 풀어 G5가 왜이렇게 어렵지 라고 생각했는데

dfs를 활용해 간단하게 해결도 가능한 문제였네요.

---

문제는 N개로 이루어진 수열을 M개의 그룹으로 나누었을 때 속한 수의 최댓값을 구하는 것입니다.

 

연속된 수가 최댓값이 되게 해야하는데 예를 들어 10, -4, 5이 있을 때 그룹이 1개라면 최댓값은 3개를 한번에 묶은 11, 그룹이 2개라면 10, 5를 각각 그룹으로 한 15가 됩니다.

 

이러한 상황을 고려하기 위해서는, 현재 수를 고르지 않는 경우, 현재 수가 이전값과 이어져 한 그룹인 경우, 현재 수가 새로운 그룹의 시작점인 경우, 이렇게 나눌 수 있습니다.

혹은 현재 수가 i번째 일 때 포함되지 않거나 k~i까지의 그룹이 지어져있거나로 나뉠 수 있습니다.

 

풀이 방식이 약간은 다른데 저는 후자의 방식이 생각나 그렇게 해결해보았습니다.

전자로 했다면 3차원배열이 필요했을 것 같습니다.

---

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<int> v(N+1, 0);
    vector<int> psum(N + 1, 0);
    for (int i = 1; i <= N; ++i)
    {
        cin >> v[i];
        psum[i] = psum[i - 1] + v[i];
    }

    int _min = -1e9;
    vector<vector<int>> dp(N+1, vector<int>(M+1, _min));
    dp[0][0] = 0;
    for (int i = 1; i <= N; ++i)
    {
        for (int j = 0; j <= M; ++j)
        {
            dp[i][j] = max(dp[i][j], dp[i - 1][j]);

            for (int k = 1; k <= i; ++k)
            {
                int cur = psum[i] - psum[k - 1];
                if (j+1 <= M)
                    dp[i][j + 1] = max(dp[i][j + 1], dp[k - 1][j] + cur);
            }
        }
    }

    cout << dp[N][M];
    return 0;
}

 

반복적으로 누적합을 사용하게 되길래 아예 누적합용 배열을 만들고 미리 저장해놓아 사용했습니다.

dp 점화식을 보면, 이전 그룹이 k-1까지 인경우 + 현재 그룹이 k~i인 경우를 통해 현재 위치에서의 최적의 값을 찾았습니다.

---

다만 N,M이 20보다 작은 굉장히 작은 범위이기에, dfs식을 만들면 간단하게 해결이 가능했겠네요