[백준 5549] 행성 탐사

[ 백준 5549 : 행성 탐사 ]


백준에 기본 DP문제 중
[백준 11660 : 구간 합 구하기 5 ] 이 문제와 똑같은문제입니다.

(A,B)~(C,D)의 직사각형안에 있는 J와 O와 I의 갯수를 뽑아야합니다.
한 좌표마다 그 전 까지의 상태를 저장해놓고 출력하는 문제인데
이번 문제는 한 좌표마다 3개의 상태를 저장해야하니까 SUM[X][Y][3]이런식으로 저장하면됩니당

그럼 상태는 어떻게 정의될까 한번 식으로 봐보면

SUM[X][Y] = 현재좌표 + SUM[X-1][Y] + SUM[X][Y-1] - SUM[X-1][Y-1]

사각형이 (0,0)~(X,Y)라고 했을때
현재좌표 + (X-1,Y)까지의 상태 + (X,Y-1)까지의 상태 - 겹치는부분(X-1,Y-1) 이렇게하면
현재좌표마다의 총 합이 구해집니다.

그럼 (A,B)~(C,D)의 합은????
현재 좌표마다 (0,0)~(C,D)까지의 합들이 구해져있으니까 (0,0)~(C,D)-(0,0)~(A,B)를 해주면됩니다.
식으로 표현하면

=>SUM[C][D] - SUM[A-1][D] - SUM[C][B-1] + SUM[A-1][B-1]

(C,D)까지의 합에서 0부터 A행위까지의 합을 빼고 0부터 B열왼쪽까지의 합을 빼고 겹치는 부분을 빼줬으니 다시 더해줍니다.(A-1,B-1)

이런식으로 풀면 답이 뽜봣!