티스토리 뷰
728x90
문제 링크
풀이
3대의 기관차가 항상 같은 수의 객차를 끌게 됩니다.
결국 N개중 3개의 시작점을 골라 최댓값을 뽑는 문제라고 생각할 수 있습니다.
기관차가 끌 수 있는 객차의 수만큼 구간을 잡고, 그 합을 미리 계산해두면 편하게 구현할 수 있습니다.
정답 코드
#include <bits/stdc++.h>
using namespace std;
int d[55'555][3];
int n, k, p[55'555], sum[55'555];
int go(int i, int cnt) {
if (cnt == 3) return 0;
if (i >= n) return 0;
int &ret = d[i][cnt];
if (ret != -1) return ret;
ret = max(go(i + 1, cnt), sum[i] + go(i + k, cnt + 1));
return ret;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> p[i];
}
cin >> k;
for (int i = 0; i < k; i++) {
sum[0] += p[i];
}
for (int i = 1; i + k - 1 < n; i++) {
sum[i] = sum[i - 1] - p[i - 1] + p[i + k - 1];
}
memset(d, -1, sizeof(d));
cout << go(0, 0);
}
728x90
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[BOJ] 백준 1673 - 치킨 쿠폰 (0) | 2021.03.30 |
---|---|
[BOJ] 백준 13544 - 수열과 쿼리 3 (0) | 2021.03.30 |
[BOJ] 백준 2169 - 로봇 조종하기 (0) | 2021.03.30 |
[BOJ] 백준 2281 - 데스노트 (1) | 2021.03.30 |
[BOJ] 백준 2306 - 유전자 (0) | 2021.03.30 |
댓글