[ Problem Solving :: 백준 ] 2616 / 소형기관차

# Link

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

2616번: 소형기관차

 

 

# Code - C++

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'
#define len(x) (int)(x).length()
#define size(x) (int)(x).size()
#define str(x) to_string(x)
#define error logic_error("line " + str(__LINE__))

// Set up : Definitions
const int MAX = 50'000;

// Set up : Global Variables
int N, M;
int A[MAX+1];
int PS[MAX+1];
int dp[MAX+1][3+1];

// Set up : Functions Declaration
int f(int idx, int cnt);


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    cin >> N;
    for (int i=1; i<=N; i++)
        cin >> A[i];
    cin >> M;

    // Process
    memset(dp, -1, sizeof(dp));
    for (int i=1; i<=N; i++) {
        PS[i] = A[i] + PS[i-1];
    }

    int ans = f(N, 3);

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
int f(int idx, int cnt)
{
    if (cnt == 0 || idx < M) return 0;
    if (dp[idx][cnt] != -1) return dp[idx][cnt];

    int tmp1 = f(idx-1, cnt);
    int tmp2 = f(idx-M, cnt-1) + (PS[idx] - PS[idx-M]);

    return dp[idx][cnt] = max(tmp1, tmp2);
}

 

 

지적, 조언, 첨언 모두 환영합니다!!!