알고리즘 & BOJ 2616 소형기관차(C++)

1019 : 소형기관차

제한시간: 1000 ms    메모리제한: 64 MB
해결횟수: 665 회    시도횟수: 1995 회   

기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨신 적은 수의 객차만을 끌 수 있다. 

기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까하는 문제를 고민하다가 다음과 같이 하기로 결장하였다.

① 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다.
② 소형 기관차 3대를 이용하여 최대한 많은 손님을 목적지까지 운송하도록 한다. 각 객차 마다 타고 있는 손님의 수는 미리 알고 있고 다른 객차로 손님들이 이동하는 것은 허용하지 않는다.
③ 각 소형 기관차는 번호가 연속적으로 이어진 객차를 끌게 한다. 객차는 기관차 바로 뒤에 있는 객차부터 시작하여 1번 부터 차례로 번호가 붙어있다.

예를 들어 기관차가 끌고 가던 객차가 7칸이고 소형 기관차 1대가 최대로 끌 수 있는 객차 수는 2칸이라고 하자. 그리고 1번 부터 7번까지 각 객차에 타고 있는 손님의 수가 아래 표와 같다고 하자. 괄호속에 있는 숫자는 객차 번호를 나타낸다. 

 

소형 기관차 3대는 각각 1-2번, 3-4번, 그리고 6-7번 객차를 끌고 가면 손님 240명을 운송할 수 있고 이보다 많은 수의 손님을 운송할 수 없다. 

기관차가 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수 그리고 소형 기관차가 최대로 끌수 있는 객차의 수가 주어질 때 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 프로그램을 작성하시오.

 

입력파일의 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다.
둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있는 손님의 수는 100명 이하이고, 입력되는 숫자들 사이에 빈칸이 하나씩 있다.
셋째 줄에는 소형 기관차가 최대로 끌 수 있는 객차의 수가 입력된다. 그 수는 기관차가 끌고 가던 객차 수의 1/3보다 적다.

한 줄에 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 출력한다.

[Copy] 7 35 40 50 10 30 45 60 2

[Copy] 240

출처 : KOI 전국 2003 초3

?

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35

/**************************************************************     Problem: 1019     User: a132034     Language: C++     Result: Success     Time:8 ms     Memory:2816 kb ****************************************************************/     #include    <iostream> #include    <algorithm> using namespace std; int T[55555]; int D[4][55555]; int main() {     int N, M;     ios::sync_with_stdio(false);     cin >> N;     for (int i = 1; i <= N; ++i)     {         int tmp;         cin >> tmp;         T[i] = T[i - 1] + tmp;     }     cin >> M;       for (int i = 1; i <= 3; ++i)         for (int j = i * M; j <= N; ++j)             D[i][j] = max(D[i][j-1], (T[j] - T[j - M]) + D[i - 1][j - M]);       cout << D[3][N];     return 0; }

BOJ 링크

간만의 알고리즘 풀이... 

이 문제는 사실 아주 예전에 도전해보았으나 결국 포기했던 문제였는데 다시 도전해봐도 역시 어려웠다... 

분명 실력이 발전하긴 한거같은데 아주 찔끔 발전했나보다... ㅠㅠ

이 문제는 다이나믹 프로그래밍이기는 한데 

약간 점진적인 방법이라고 해야하려나... 

D[i][j]는 i번째 소형기관차로 1~j번째 객차칸을 끌 때 최대로 운송할 수 있는 승객 수라고 생각하였다.

==> 구하려는 목표는 D[3][N]이 된다. 

사실 하도 못풀겠어서 고수님께 얻은 힌트가

D[1][i]는 1~i번째 객석까지 왔을 때 1번 기관차가 끌 수 있는 최대 승객 수

2번 기관차는 1번을 보면 된다.. 

였다.

상당히 결정적이지만 풀고나니 맞는말인데 풀기전엔 도저히 무슨말인지... 

아무튼 

D[i][j]를 결정했고, 힌트까지 결합한다면 순서는 분명 

1번 기관차 -> 2번 기관차 -> 3번 기관차 순서로 풀어야 할 것이다. (힌트에서 2번 기관차는 1번 결과를 보라고 하였으므로..)

29 line의 for loop를 위와같은 이유 때문에 써 주었다. 

아래 for loop는 결국 

i번째 기관차에서 이전 객차까지의 최대값(D[i][j-1]과 현재 객차를 포함했을 떄의 최대값(T[j] - T[j-M]) + D[i-1][j-M] 중 큰 값이 i번째 기관차가 1~j객실중 끌 수 있는 승객의 최대값이 된다. 

좀더 자세히 설명하자면 

D[i][j-1]은 앞서 말한대로 i번째 기관차가 1~j-1번 객차까지 중 가장 많은 승객을 끌 수 있는 경우의 승객수가 될 것이고

(T[j] - T[j-M]) + D[i-1][j-M]은 T[j]가 입력받을 때 1번~j번째 객차까지의 모든 승객수이므로 

T[j] - T[j-M]은 결국 j-M번째 객차부터 j번째 객차까지의 승객수가 될 것이다. (j번째 객차를 포함하며 기관차가 최대로 끌 수 있는 객차만큼)

+ D[i-1][j-M]은 1번객차의 경우 사실 필요없다.(0이므로)

뜻은 이전 객차(i번째 객차가 현재 2번 객차라면 i-1은 1번 객차)에서 1~j-M까지의 객차 중 선택할 수 있는 최대의 승객이 된다. 

j-M인 이유는 당연하지만 현재 객차에서 j-M+1~j번 객차를 끌고가므로 i-1번째 객차에서는 j-M번째 객차까지만 끌 수 있기 때문이다. 

이렇게 연산하다 보면 D[3][N]을 구할 수 있다. 

(30번째 for loop의 j는 i * M으로 했으나 사실 i로 해도 1로 해도 될 것 같다. 연산량을 매우매우 조금이라도 줄이기 위함...)