알고리즘 공부
백준 2616번 : 소형기관차
EQ1
2020. 5. 9. 19:47
'뭐야? 이 문제 쉽잖아? 살짝 변형하면 어디서 본 것 같은데?'라고 생각했다가 '시간 초과'나고 '틀렸습니다' 뜨고... ㅎㅎ 왜 항상 어디서 본 것 같은데 틀리는 것일까... 흠...
풀이
처음에 dp를 정할 때 조금 헷갈렸다. 보통 변하는 값 2개를 dp의 한 축으로 두는 경우가 많아서 '소형 기관차의 개수는 3개로 고정이니까 그거 말고 다른 것을 dp의 축으로 둬야지 ^^!'라고 생각한 게 오판이었다.
dp [i][j] : 소형 기관차가 i개 있고 객실이 j번까지 있을 때 운송가능한 최대 승객 수
그 외의 변수를 정의하고 가면
n : 총 객실 수
m : 소형기관차가 끌 수 있는 최대 객실 수
sum [k] : 1번 객실부터 k번 객실까지 승객의 총합
소형 기관차가 i-1개였다가 1개 추가되서 i개가 되는 상황을 생각해보자. i번째 소형기관차는 최대 m개의 객실을 끌 수 있으므로 j-m+1번 객실부터 j번 객실 까지를 운송할 수 있다. 그리고 나머지 1번부터 j-m번 객실은 기존의 i-1개의 소형기관차가 운송하면 된다.
dp [i][j] = sum [j] - sum [j-m] + dp [i-1][j-m]
하지만 i번째 소형 기관차가 j-m+1번부터 j번까지의 객실을 끄는 것이 최선이 아닐 수도 있다. 다시 말해 j번째 객실을 운송하지 않는 것이 최선일 수도 있다.
dp [i][j] = max( dp [i][j-1], sum [j] - sum [j-m] + dp [i-1][j-m] )
#include <iostream>
using namespace std;
int n, m;
int seq[50002];
int dp[4][50002];
int sum[50002];
int main()
{
ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for(int i = 1; i <= n; i++)
{
cin >> seq[i];
sum[i] = sum[i-1] + seq[i];
}
cin >> m;
for(int i = 1; i <= 3; i++)
{
for(int j = i*m; j <= n; j++)
{
dp[i][j] = max(dp[i][j-1], sum[j] - sum[j-m] + dp[i-1][j-m]);
}
}
cout << dp[3][n];
return 0;
}