백준 2616. 소형기관차

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

2616번: 소형기관차

 

d[i][j] = i 번째 소형기관차까지 있을때, j 번째 객차까지 있을때의 최대 운송 손님 수 

 

d[i][j] = max(d[i-1][j-M] + (preSum[j] - preSum[j-M]), d[i][j-1])

 

35	40	50	10	30	45	60
	75	90	90	90	90	105
			135	135	165	195
					210	240

소형기관차가 최대로 끌고 갈 수 있는 객차의 수 = 2 

 

 

d[2][6] 은 2번째 소형기관차까지 있을때, 6번 객차까지 있을때의 최대 운송 손님 수이다.

 

2번째 소형기관차가 6번째 객차를 선택한다고 하면,

= 1번째 소형기관차가 4번째 객차까지 검사한 d[1][4] + (5번객차 손님수 + 6번객차 손님수) 

 

2번째 소형기관차가 6번째 객차를 선택하지 않는 경우인 

= d[2][5] 

 

둘 중 큰 값이 d[2][6] 이 된다.