백준 5549, 행성 탐사

개요

문제 링크
골드 5, 누적합, DP
2차원 구간 내에 존재하는 문자의 개수 구하기

---

접근

1. 2차원 경로탐색 DP와 매우 유사하다. 누적합이라도 결국 인접한 원소를 이용하는 것은 동일해서 DP로 분류했다.
2. 우선 기본적인 누적합. 만약 1차원 배열에서 i부터 j까지 누적합을 구한다면 어떻게 할까? sum[1,j] - sum[1,i-1]을 해주면 된다.
3. 동일하게 2차원에서 [y1,x1]부터 [y2,x2]까지의 누적합을 구한다면 sum[y2,x2]-sum[y2,x1-1]-sum[y1-1,x2]+sum[y1-1,x1-1]을 해주면 된다. 전체 합-왼쪽까지 합-위까지 합+왼쪽위까지 합을 해주는 것인데, 벤다이어그램을 생각하면 쉽다.
   만약 A∪B를 구한다면 A+B-A∩B를 해줘야 한다. 어떤 C가 A,B를 포함한다면 C이면서 A,B가 아닌 부분은 C-(A+B-A∩B)를 해주면 된다.

---

Pseudo code

for (y = 세로)
    for (x = 가로)
        dp[y][x] = dp[y-1][x]+dp[y][x-1]-dp[y-1][x-1]
        dp[y][x] += J / O / I

answer = dp[y2][x2]
answer -= dp[y2][x1-1] + dp[y1-1][x2] - dp[y1-1][x1-1]

---

Source code

#include <iostream>
#include <array>
using namespace std;

typedef array<int,4> node;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    node a[n+1][m+1];
    char s[m+1];
    for (int i=0; i<=n; i++)
        for (int j=0; j<=m; j++)
            a[i][j] = {0,0,0,0};
    for (int i=1; i<=n; i++) {
        scanf("%s", s+1);
        for (int j=1; j<=m; j++)
            a[i][j][3] = s[j];
    }
    string b = "JOI";
    for (int i=1; i<=n; i++)
        for (int j=1; j<=m; j++)
            for (int k=0; k<3; k++) {
                a[i][j][k] = a[i-1][j][k]+a[i][j-1][k]-a[i-1][j-1][k];
                a[i][j][k] += a[i][j][3]==b[k];
            }
    int x,y,p,q;
    for (int i=0; i<k; i++) {
        scanf("%d%d%d%d",&y,&x,&p,&q);
        x--, y--;
        for (int j=0; j<3; j++)
            printf("%d ",a[p][q][j]-a[y][q][j]-a[p][x][j]+a[y][x][j]);
        printf("\n");
    }
}