BOJ :: [2616] 소형기관차(C++)

문제

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

2616번: 소형기관차

문제 요약

기차는 한대의 기관차와 여러 대의 객차로 구성되어있다. 만약 운행 중 기관차가 고장 난 다면 다른 기관차가 와서 객차를 끌고 목적지까지 운행해야 한다. 철도청에서는 기관차가 고장 날것을 대비해 k개의 객차만 끌 수 있는 소형 기관차 3대를 배치했다. 총 n개의 객차가 있을 때 3대의 소형 기관차가 가장 많은 인원을 데리고 목적지까지 도착할 수 있는 방법을 찾아야 한다. k개의 객차를 끌고 갈 때 연속된 객차만 끌고 갈 수 있다. 예를 들어 k가 4일 때 1번 객차를 선택한 경우, 1-2-3-4만 가능하다.

풀이

이 문제는 누적합과 DP로 해결할 수 있다. 문제를 보고 누적합을 이용해야겠다고 생각했다. 객차가 최대 50,000개이기 때문에 모든 경우의 수를 다 볼수도 없다. DP문제인 거 같은데 어떻게 점화식을 세워야 할지 몰라서 정답을 보고 코드를 완성했다.

배열 ps는 누적합을 나타내는 배열로, 각 객차까지의 승객 수의 합을 저장하고 있다. dp배열은 dp[소형 기관차 번호][객차 번호]로 만들었다. 소형 기관차 번호를 i, 객차 번호를 j라고 가정하면 dp[i][j]는 i번째 소형 기관차가 j번째 까지 객차를 끌고 갈 때 데려갈 수 있는 인원수를 저장한다. 우리가 누적합을 구해놓았기 때문에 j번째 객차를 선택했을 때 데려갈 수 있는 인원수는 누적합 배열에서 j-k번째 값을 빼주면 j-k ~ j번째 객차를 끌고 갈 때 데려갈 수 있는 인원수를 구할 수 있다. 첫 번째 소형 기관차부터 세 번째 소형 기관차까지 차례대로 구해준다. 두 번째 기관차부터는 이전 기관차가 선택한 객차를 신경 써야 한다. 이전 기관차가 j번째 객차를 끌고갔다면 다음 기관차는 j+k번째 기관차를 끌고 갈 수 있다. 따라서 2번째 차가 j번째 객차를 선택하려면 i-1번째 기관차는 j-k번째까지 객차를 선택할 수 있다. 우리는 미리 이전 기관차가 j번째 객차를 선택했을 때 데려갈 수 있는 인원수 중 최댓값을 구해놨기 때문에 dp[i-1][j-k]로 i-1번째 객차가 j-k번째 객차를 끌고 갈 때의 값에 i번째 객차가 끌고 갈 j번째까지의 객차의 인원수 (ps[j] - ps[j-k]) 값을 더해 i번째 기관차의 최대 인원수를 구할 수 있다.

코드

#include <iostream>

using namespace std;
int ps[50001] = {0,};
int dp[4][50001] = {0,};
int result = 0;

int main(){
    int n, k, tmp;
    cin >> n;

    for(int i = 1; i <= n; i++){
        cin >> tmp;
        //누적합
        ps[i] = ps[i-1] + tmp;
    }

    cin >> k;
	
    //dp배열을 구하는 부분 - 객차는 1번부터 3번까지
    for(int i = 1; i <= 3; i++){
    	//j번째까지의 객차를 선택하기 때문에 i*k번째 객차부터 선택
        for(int j = i * k; j <= n; j++){
                dp[i][j] = max(dp[i][j-1], dp[i-1][j-k] + ps[j] - ps[j-k]);
        }
    }

    cout << dp[3][n] << endl;
    return 0;
}

 

 

작성한 글에 잘못된 부분이나 문제가 있는 경우 댓글에 작성해 주시면 수정하도록 하겠습니다. 질문도 환영합니다! :)