[ BOJ 백준 2616번 - 소형기관차 ] 해설 및 코드

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

목적

소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하자.

 

접근법

1. s[i][j]는 i번째 객차부터 j번째 소형 기관차로 손님을 운송할 때의 최대값으로 정한다.

2. 그러면 i번째 객차를 끄는 경우와 i + 1번째 객차부터 끄는 경우의 최대값을 취하게 된다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;++i)
#define N 50000
using namespace std;
 
int n, a[N],b[N], k, s[N][3];
 
int sol(int i, int j) {
    if (i + k > n || j == 3)return 0;
 
    int& ref = s[i][j];
    if (ref != -1)return ref;
 
    return ref = max(sol(i + 1, j), b[i] + sol(i + k, j + 1));
}
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    memset(s, -1, sizeof(s));
    cin >> n; 
    f(i, 0, n)cin >> a[i]; 
    cin >> k;
 
    b[0] = a[0];
    f(i, 1, k)b[0] += a[i];
    f(i, 1, n - k + 1) b[i] = b[i - 1] + a[i + k - 1] - a[i - 1];
 
    cout << sol(0, 0);
    return 0;
}

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.