[백준/BOJ] 5549번 - 행성탐사

오랜만의 글 이네요.

백준 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구역, 탐사해야할 영역, A, B, C로 나누어져있다면,

탐사하려는 영역의 결과는 0,0 부터 끝까지, 즉 A + B + C + 탐사영역으로 이루어져있습니다.

dp 배열에 저장된 값 역시 누적합입니다.

이때 dp 배열에 저장된 값에서 B, C, A를 빼준다면 원하는 부분 합이 나오겠지요.

단, B, C에 저장되어 있는 값은 A와 B의 누적합, A와 C의 누적합이므로

B, C를 빼주게 되면 A를 두번 뺀 결과가 얻어지니, 다시 A를 더해줘야합니다.

 

 

간단하네요.

수고하세용 :)