[BOJ] 14595번: 동방 프로젝트

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

편의상 벽을 허문다고 생각하는 대신 x부터 y-1 사이의 모든 방에 마킹을 해둔다고 생각해봅시다. 그러면 문제에서 요구하는 답은 곧 마킹이 되어있지 않은 방의 수임을 알 수 있습니다.

O(N^2) 솔루션은 직접 x, y-1의 모든 방에 마킹을 함으로서 얻을 수 있고, O(N)은 직접 마킹을 하는 대신 D[x]++, D[y]--를 통해 마킹을 처리합니다. 

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