[BOJ] 1756번: The Disks

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

딱 보면 뭔가 stack의 느낌이 확 듭니다. 시간을 O(N+M)으로 만들기 위해 이래저래 고민을 하다 보면, stack 내에 현재 디스크의 크기, 그 디스크가 최대한 깊게 들어갈 수 있는 깊이를 저장하면 되겠다는 것을 알 수 있습니다.

 예를 들어 5, 6, 2, 2, 4는 사실 5, 5, 2, 2, 2와 다를 것이 전혀 없고 이를 (5, 2), (2, 5)로 두겠다는 것입니다.((2, 5)가 stack의 top) 이제 디스크가 들어올 때 마다 top의 디스크의 크기와 비교해 top의 디스크의 크기가 작다면 pop을 합니다. 이렇게 해서 해당 디스크가 담길 수 있는 공간을 찾고나면 깊이를 1 감소시킵니다.

이 때 (3, 4), (2, 6)에서 2 2 2 2 2 3이 들어왔는데 답을 4라고 출력하지 않기 위해 최근에 담긴 디스크가 있는 높이를 저장하고 있는 것이 도움이 됩니다.

https://github.com/blisstoner/BOJ/blob/master/1756.cpp