백준 15724번 주지수

문제 링크입니다: https://www.acmicpc.net/problem/15724

bottom-up DP 문제였습니다.

1,1,3,2일 때 region[3][2]+(초록색 직사각형 + 파란색 직사각형 - 하늘색 직사각형)을 하면 범위 내에 있는 사람들의 수를 모두 구할 수 있습니다.

그리고 주의할 점은 endl은 시간이 오래걸리기 때문에 시간초과가 발생합니다. 따라서 "\n"을 사용해서 개행을 해줘야합니다.

#include <iostream>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1024 + 1;

 

int N, M;

int region[MAX][MAX];

int cache[MAX][MAX];

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상 위해

        cin >> N >> M;

 

        //[x][y] 구역에 사는 사람들의 수와

        //[1 ~ x-1][1 ~ y]의 범위에 있는 사람들의 수 + [1 ~ x][1 ~ y-1]의 범위에 있는 사람들의 수를 더하고

        //위 범위에서 겹치는 [1 ~ x-1][1 ~ y-1]의 범위에 있는 사람들의 수를 뺀다

        for (int x = 1; x <= N; x++)

                 for (int y = 1; y <= M; y++)

                 {

                         cin >> region[x][y];

                         cache[x][y] = region[x][y] + (cache[x - 1][y] + cache[x][y - 1] - cache[x - 1][y - 1]);

                 }

 

        int K;

        cin >> K;

 

        for (int i = 0; i < K; i++)

        {

                 int x1, x2, y1, y2;

                 cin >> x1 >> y1 >> x2 >> y2;

 

                 //앞서 사용한 기법과 마찬가지로

                 cout << cache[x2][y2] - (cache[x1 - 1][y2] + cache[x2][y1 - 1] - cache[x1 - 1][y1 - 1]) << "\n"; //endl 쓰면 시간초과

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~