쓰레기 압축

미하엘 엔데의 소설 「모모」에 등장하는 청소부 베포 할아버지는 매일 길에서 쓰레기를 줍고 주운 쓰레기는 쓰레기통에 넣는다. 그에게는 무한히 많은 갯수의 쓰레기통이 있는데, 이 쓰레기통들은 조금 특별하다. 일반 쓰레기통과 달리 이 쓰레기통은 들어있는 쓰레기들을 자동으로 압축하며, 지금까지 담겨져 있는 쓰레기 중에서 지금 넣는 쓰레기의 무게보다 가벼운 쓰레기는 모두 압축된다. 예를 들어,

위 그림처럼 위에서부터 3, 4, 6의 무게를 지닌 쓰레기가 담겨있는 쓰레기통에 5의 무게를 가지는 쓰레기를 넣을 경우, 5보다 가벼운 3, 4는 자동으로 압축되어 사라진다. 물론, 무한히 많은 갯수의 쓰레기통이 있기 때문에, 새로운 쓰레기통에 쓰레기를 담는 것도 언제든 가능하다. 단, 쓰레기는 줍는 순서대로 처리해야 한다. 쓰레기의 순서를 바꾸려 한다면, 회색신사가 베포 할아버지의 시간을 훔쳐간다 (👻).

베포 할아버지는 쓰레기를 모두 청소한 후, 쓰레기통에서 쓰레기를 모두 꺼내 한 곳에 모아 무게를 잰다. 쓰레기를 청소할 때 어떻게 담는가에 따라 가능한 무게는 여러가지일 수 있지만, 베포 할아버지는 달인이기 때문에 항상 최종 무게를 가장 적게 만든다.

입력으로 N개의 원소를 가지는 쓰레기의 무게 정보 배열이 주어진다 (N은 백만 이하의 자연수, 각 원소는 백만 이하의 자연수). 쓰레기를 배열의 인덱스가 빠른 순서대로 처리할 때, 베포 할아버지가 확인하는 최종 무게의 값을 출력하시오. (제한시간: 1초)

예시1)

[6,4,3,5]

출력: 11

예시2)

[4,3,1,2]

출력: 9

*회고: 화장실에서 쓰레기통을 청소하는 아주머니를 보고 떠올린 문제. 스토리 구성에 억지스러움이 있다. 그리고 생각보다 스택으로 쉽게 풀려버린다. 다른 조건을 나중에 추가하자.