문제) 백준 - 누적 합 - 어두운 건 무서워
https://www.acmicpc.net/problem/16507
16507번: 어두운 건 무서워
첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사
www.acmicpc.net
쿼리(Q)의 최대 개수가 10000이고 R과 C의 최대가 1000이기에 매번 합을 탐색하면 O(Q*R*C)의 시간 복잡도로 해결할 수 없습니다. 따라서, 사진의 크기의 합을 미리 저장해 좌표가 주어지면 O(1) 안에 쿼리를 처리할 수 있는 누적합을 이용해 해결해야 했습니다.
C++ 소스코드)
Full Code)
GitHub - Chocochip101/BOJ_Solution: BOJ Solutions
BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHub.
github.com
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
| [백준] 11365번 - !밀비 급일 (C++) 문제 및 풀이 (0) | 2022.02.03 |
|---|---|
| [백준] 7511번 - 소셜 네트워킹 어플리케이션 (C++) 문제 및 풀이 (0) | 2022.01.30 |
| [백준] 14467 - 소가 길을 건너간 이유 1 (C++) 문제 및 풀이 (0) | 2022.01.29 |
| [백준] 22942번 - 데이터 체커 (C++) 문제 및 풀이 (0) | 2022.01.29 |
| [백준] 17128번 - 소가 정보섬에 올라온 이유 (C++) 문제 및 풀이 (0) | 2022.01.28 |
댓글