Logo냥냠감자기술 블로그
Skip to Content
AlgorithmDP (31)소형기관차
작성일: 2024-01-12

문제

백준 2616 - 소형기관차 

  • 난이도: 골드3
  • 알고리즘: DP, 부분합

코드

#include <iostream> #include <vector> using namespace std; vector<vector<int>> cache(50001, vector<int>(3, -1)); vector<int> sumValue; int getMax(int smallLinked, int index, int picked) { if(picked==3) { return 0; } if(index>=sumValue.size()) { return -987654321; } int& ret=cache[index][picked]; if(ret!=-1) return ret; ret=-987654321; ret=max(sumValue[index]+getMax(smallLinked, index+smallLinked, picked+1), getMax(smallLinked, index+1, picked)); return ret; } int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin>>n; vector<int> value(n); for(int i=0; i<n; i++) { cin>>value[i]; } int smallLinked; cin>>smallLinked; int smallSum=0; for(int i=0; i<smallLinked; i++) { smallSum+=value[i]; } sumValue.push_back(smallSum); for(int i=smallLinked; i<n; i++) { smallSum+=value[i]; smallSum-=value[i-smallLinked]; sumValue.push_back(smallSum); } cout<<getMax(smallLinked, 0, 0); }

회고

역시 군대가 공부하기 좋은 환경은 아닌 것 같다… 주위가 너무 시끄러워 집중을 하지 못해 푸는데 꽤나 많은 시간이 걸렸다. 우선 부분합을 이용해 소형 기관차가 끌 수 있는 길이의 열차를 묶어 그 안에 탈 수 있는 승객의 수를 저장하는 벡터를 n의 시간에 구할 수 있었다

이 문제는 푸는 방식에 따라 시간초과가 날 수도 있는 문제이다. 나는 cache[i][j]=i번째 이후로 j번째 소형 기관차가 끌 열차 그룹을 고를 때 태울 수 있는 최대 승객의 수를 저장하도록 했다.

이때 cache[i][j]=max(cache[i+소형기관차가 끌 수 있는 열차 길이][j]+[i]번째 열차그룹에 태울 수 있는 승객 수, cache[i+1][j])가 된다. 만약 cache[i][j]를 i번째 열차를 j번째 소형 기관차가 끌 때 태울 수 있는 승객의 최소값으로 정한다면, 반복문을 사용하여야 한다. 소형 기관차가 끌 수 있는 열차 길이를 k라고 한다면 cache[i][j]=max(cache[i+k][j+1], cache[i+k+1][j+1], cache[i+k+2][j+1] …)+[i]번째 열차 그룹에 태울 수 있는 승객 수 가 된다. 이때 두번째 방법으로 풀이한다면 반복문이 사용되어 최대 3*n개의 부분문제가 존재하고, 한 부분문제가 O(n)의 시간에 계산되므로, n이 최대 5만인 이 문제에서는 시간초과를 발생시킨다.