[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

'알고리즘 > BOJ' 카테고리의 다른 글

[BOJ] 1214번: 쿨한 물건 구매  (0) 2018.05.24
[BOJ] 13258번: 복권 + 은행  (0) 2018.05.24
[BOJ] 14867번: 물통  (0) 2018.05.23
[BOJ] 3190번: zmjia  (0) 2018.05.17
[BOJ] 14956번: Philosopher's Walk  (5) 2018.05.17
[BOJ] 14585번: 사수빈탕  (0) 2018.05.17
  Comments