[백준] 16507번 - 어두운 건 무서워 (C++) 문제 및 풀이

문제) 백준 - 누적 합 - 어두운 건 무서워

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

16507번: 어두운 건 무서워

 

쿼리(Q)의 최대 개수가 10000이고 R과 C의 최대가 1000이기에 매번 합을 탐색하면 O(Q*R*C)의 시간 복잡도로 해결할 수 없습니다. 따라서, 사진의 크기의 합을 미리 저장해 좌표가 주어지면 O(1) 안에 쿼리를 처리할 수 있는 누적합을 이용해 해결해야 했습니다.

 

C++ 소스코드)

 

Full Code)

https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/16507_%EC%96%B4%EB%91%90%EC%9A%B4%20%EA%B1%B4%20%EB%AC%B4%EC%84%9C%EC%9B%8C.cpp

GitHub - Chocochip101/BOJ_Solution: BOJ Solutions