내일은 어딘가로 떠나서 문제를 못 풀고… 그러니까 양심 챙기자는 마음으로 골드(5ㅋ)에서 하나 랜덤으로 골라잡음…

정답 비율 높아서 골랐는데…ㅋㅋㅋㅋㅋㅋㅋㅋㅋ 문제도 뭐 되게 익숙하게 생겼고… 풀이도 처음에는 그래프 탐색인가 했다가 시간 제한 1촌데 테케 십만개는 좀 아닌 거 같아서 dp구나…하고 바로 떠올림

그 구간 합 구하는 dp처럼 풀면 될 거 같음 대신 합이 3종류인 걸로ㅋㅋㅋ 1x3 배열이 mxn크기 배열 한 칸 한 칸마다 들어있다고 하고 짜면 될 거 같음

3차원 벡터… 별 건 아닌데 은근 헷갈린다.

이 링크의 도움을 받아서 작성했다. 링크

무난히 맞았다… 일단 코드

#include <iostream>
#include <vector>

using namespace std;

void dp(const vector<vector<char>>& input, vector<vector<vector<int>>>& cnt, int m, int n) {
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 0; k < 3; k++) {
                cnt[i][j][k] = cnt[i-1][j][k] + cnt[i][j-1][k] - cnt[i-1][j-1][k];
            }

            switch(input[i][j]) {
                case 'J' :
                    cnt[i][j][0]++;
                    continue;
                case 'O' :
                    cnt[i][j][1]++;
                    continue;
                case 'I' :
                    cnt[i][j][2]++;
                    continue;
            }
        }
    }
}

void calcAnswer (const vector<vector<vector<int>>>& cnt, vector<int>& answer, int a, int b, int c, int d) {
    for (int i = 0; i < 3; i++) {
        answer[i] = cnt[c][d][i] - cnt[a-1][d][i] - cnt[c][b-1][i] + cnt[a-1][b-1][i];
    }
}

int main() {
    ios_base ::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int m, n, k, a, b, c, d;

    cin >> m >> n >> k;
    vector<vector<char>> input (m+1, vector<char> (n+1, ' '));
    vector<vector<vector<int>>> cnt (m+1, vector<vector<int>> (n+1, vector<int> (3, 0)));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> input[i][j];
        }
    }
    dp(input, cnt, m, n);

    while (k--) {
        cin >> a >> b >> c >> d;
        vector<int> answer (3, 0);
        calcAnswer(cnt, answer, a, b, c, d);
        for (int num : answer) {
            cout << num << ' ';
        }
        cout << '\n';
    }
}

그 칸까지 누적 합 더해준 다음에 어디 칸 알고 싶다 하면 그 칸 범위만 또 계산해가지고 리턴해줬다… 매우 간단

다른 사람들은 메모리를 덜 먹어서 왜 그런가 보니까 벡터 대신에 그냥 배열 쓰고 정답도 배열로 안하고 그냥 상수로 리턴하면 좀 메모리 덜 먹는 듯…

그 외에는 시간 줄이려면 처음에 지도 입력받을 때 같이 덧셈을 해버릴 수도 있음… 이건 입출력 분리하겠다고 일부러 따로 한 거긴 한데 나중에 대회 나가거나 할 때는 이게 더 유용할 듯… 참고해야겠음