막대 접기 timer 1s memory 1024MB

N개의 막대기가 경첩을 통해 일자로 연결된 큰 막대기가 있다. 이 경첩을 180도 접는 동작을 통해, 전체 막대기의 길이를 최소화하려고 한다.

구체적으로, 가장 왼쪽 경첩부터 시작해 이 부분에서 접을지 접지 말지를 결정한다. 만약 접지 않는다면, 그 다음 오른쪽 경첩으로 이동한다. 접는다면, 경첩 왼쪽에 있는 모든 부분을 시계방향으로 180도 접는다.

그러나 예를 들어 각 막대기의 길이가 4, 3, 2이고, 4와 3 사이 경첩을 접은 상태에서 3과 2 사이 경첩을 접으려 시도한다면 길이 4 막대기가 부러지게 된다. 지금 경첩이 있는 위치를 전에 접은 막대기가 덮고 있었기 때문에 물리적으로 접을 수 가 없는 것이다.

막대기가 부러지지 않도록, 그러면서도 최종 상태의 전체 막대기의 길이가 최소가 되도록 경첩을 접어보자.