BOJ 2616 소형 기관차

이 문제는 내가 풀었던 문제로 되어있는데, dp로 짜는데도 좀 오래걸렸고, 그마저도 결국 시간초과를 받았다. 음 어떻게 짜야할까?
처음에 풀 때는
 d[num][train] = num번째의 객차부터 묶어서 소형 기관차로 옮길 때, 소형 기관차는 train개 남았을 때, 운송할 수 있는 최대 손님의 수
이렇게 하면 시간초과가 날 수 밖에 없다. num이 50000, train은 3이지만, dp함수 안의 for문이 num정도.. O(n제곱)...

그렇다면 1차원 배열로 접근해볼까?
d[num] = num번째 객차부터 묶어서 소형 기관차로 옮길 때, 운송할 수 있는 최대 손님의 수
근데 이렇게 하더라도 만약 기관차가 최대로 끌 수 있는 객차의 수가 1이거나 매우 작으면 O(n제곱)이 될 것 같은데...

아 이걸 어떻게 푼거지 ... 1분만 더 고민해보고 내 코드를 봐야겠다.

질문 게시판의 답변을 보니 for문을 없애야 한다는(그래야 시간복잡도를 줄일 수 있다는) 답변이 있는데, 내 코드를 보니 정말 for문이 없다. 일단 2차원 배열을 이용하였는데, for문이 없다.
아... 이 것은 현재 해당하는 객차를 시작으로 선택을 할 것인지 아니면 선택하지 않고 넘어갈 것인지로 모든 경우를 나눈다.
모든 경우는 기관차로 현재 해당하는 객차를 시작으로 선택하느냐, 선택하지 않느냐로 나눠질 수 있다. 선택하는 경우는 최대로 끌 수 있는 객차수 만큼 건너뛰어보면 되고 선택하지 않는다면 다음 칸 객차를 보면되는 것이다.

뭔가 얼떨떨하다 해야되나... 같은 2차원 배열인데, 생각을 어떻게 하느냐, 접근을 어떻게 하느냐에 따라서 시간복잡도가 확 달라진다.
다시 짜봐야겠다. 음 일단 AC를 받았다. 그리고 주의해야 할 점이 주어지는 값 중에 "최대로 끌 수 있는 객차수" 가 있는데, 말 그대로 최대이므로 만약 최대로 끌 수 있는 객차수가 3이면 3미만의 객차를 끄는 경우를 생각해줘야 하는 건가 고민했는데, 3이하의 객차를 끄느니 그냥 3개를 끄는 것이 더 큰 값이다. 그리고 최대로 끌 수 있는 객차수가 전체 객차수의 1/3보다 작다고 되어있으므로 최대 손님의 수인 경우는 최대 객차수만큼 끄는 경우가 될 수 밖에 없다.
그런데 내가 좀 실수를 한 것이 있는데, 기저 조건에서 num이 (num번째 객차) n보다 크면 0을 return하는 것으로 처리했는데, 0을 return하는 것은 문제가 안되지만, 0을 return하면 그 return된 0과 더해지는 psum부분의 index역시 n보다 클 수 있으므로 배열 범위를 초과할 수 있다. 아마 그래서 틀린 것 같다.

이 문제도 배울 게 많은 좋은 문제였고 또 한 번 나의 부족한 실력을 알 수 있었다.