BOJ 백준 5561 : 과자의 분할

시작하면서

　이번 문제는 다이나믹 프로그래밍(Dynamic Programming) 문제이다.

BOJ 5561 - 과자의 분할

​

문제 이해

​ 이 문제는 추후에 다시 푼다… 어렵다

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N, input;
    vector<int> dp[2];

    cin >> N;

    dp[0].resize(N);
    dp[1].resize(N);

    for (int i = 1; i < N; i++)
    {
        cin >> input;

        for (int j = i; j > 1; j--)
        {
            dp[1][j] = min(dp[0][j - 1], dp[0][i + 1 - j] + input);
        }

        dp[1][1] = input;

        copy(dp[1].begin(), dp[1].begin() + 1 + i, dp[0].begin());
    }

    cout << dp[0][N * 0.5];

    return 0;
}