코딩 연습장

오랜만의 글 이네요. 백준 5549번 - 행성 탐사입니다. https://www.acmicpc.net/problem/5549 전형적인 구간합 문제 입니다. N x M 크기의 행성의 지도와, 조사 대상 영역 K개 각각의 양 끝 좌표가 주어집니다. 행성을 한 번 탐사하기 위해 걸리는 시간은 O(NM), 즉 모든 K에 대해 재탐사를 수행한다면 시간 복잡도는 O(KNM)이 됩니다. 따라서 탐사는 재탐사는 불가능합니다. 한 번의 탐사 결과를 기억해서 재활용합시다. 간단하게 (1, 1)부터 시작해서 (X, Y)까지 탐사 결과를 dp[ X ][ Y ]에 저장합니다. 이제 (X1, Y1)부터 (X2, Y2),까지의 탐사 결과는 구간합(prefix-sum)을 이용하여 쉽게 구할 수 있습니다. 위와 같이 N x M이 4구..