다리 건너기

문제 설명

한 마을에 강을 건너기 위한 하나의 다리가 있습니다. 이 다리는 길이 length(칸), 최대 하중 limit(kg)를 가집니다. 여러 대의 트럭이 중요한 물자를 싣고 차례대로 마을을 향해 다리를 건너려고 합니다. 트럭들은 대기열에 서 있으며, 순서가 되면 가능한 한 빨리 다리 위로 진입하려고 합니다.

다리 위에는 동시에 최대 length 대의 트럭만 올라갈 수 있고, 다리 위에 있는 트럭 무게의 합이 언제나 최대 하중 limit을 초과할 수 없습니다. 각 트럭은 1초에 한 칸씩 움직일 수 있습니다.

다리의 길이 length와 최대 하중 limit, 대기열에 서 있는 순서대로 트럭의 무게 trucks가 차례로 주어질 때 대기열에 있는 모든 트럭이 다리를 완전히 지나가기까지 걸리는 최소 시간을 반환하는 solution 함수를 작성하시오.

제한 사항

• length는 1 이상 100 이하의 자연수입니다.
• limit은 1 이상 10,000 이하의 자연수입니다.
• trucks의 길이는 1 이상 1,000 이하입니다.
• trucks의 원소는 1 이상 limit 이하의 자연수입니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 시간에 따른 대기열과 다리 상태는 아래와 같습니다.

  초	대기열	다리 상태(2칸)	비고

  | 1 | [4,5,6] | 7 - | 7kg 진입 | | 2 | [4,5,6] | - 7 | 이동 | | 3 | [5,6] | 4 - | 7kg 종료, 4kg 진입 | | 4 | [6] | 5 4 | 5kg 진입 | | 5 | [6] | - 5 | 4kg 종료 | | 6 | [] | 6 - | 5kg 종료, 6kg 진입 | | 7 | [] | - 6 | 이동 | | 8 | [] | - - | 6kg 종료, 완료 |

• 따라서 8을 반환합니다.

2번 테스트케이스 설명

• 시간에 따른 대기열과 다리 상태는 아래와 같습니다.

  초	대기열	다리 상태(3칸)	비고

  | 1 | [5,5,15] | 5 - - | 첫 번째 5kg 진입 | | 2 | [5,15] | 5 5 - | 두 번째 5kg 진입 | | 3 | [15] | 5 5 5 | 세 번째 5kg 진입 | | 4 | [15] | - 5 5 | 첫 번째 5kg 종료 | | 5 | [15] | - - 5 | 두 번째 5kg 종료 | | 6 | [] | 15 - - | 세 번째 5kg 종료, 15kg 진입 | | 7 | [] | - 15 - | 이동 | | 8 | [] | - - 15 | 이동 | | 9 | [] | - - - | 15kg 종료, 완료 |

• 따라서 9를 반환합니다.

3번 테스트케이스 설명

• 시간에 따른 대기열과 다리 상태는 아래와 같습니다.

  초	대기열	다리 상태(4칸)	비고

  | 1 | [3,7,7,5] | 10 - - - | 10kg 진입 | | 2 | [7,7,5] | 3 10 - - | 3kg 진입 | | 3 | [7,5] | 7 3 10 - | 첫 번째 7kg 진입 | | 4 | [7,5] | - 7 3 10 | 이동 | | 5 | [5] | 7 - 7 3 | 10kg 종료, 두 번째 7kg 진입 | | 6 | [] | 5 7 - 7 | 3kg 종료, 5kg 진입 | | 7 | [] | - 5 7 - | 첫 번째 7kg 종료 | | 8 | [] | - - 5 7 | 이동 | | 9 | [] | - - - 5 | 두 번째 7kg 종료 | | 10| [] | - - - - | 5kg 종료, 완료 |

• 따라서 10을 반환합니다.