백준 2167 2차원 배열의 합(dynamic programming)

 

위 코드는 dp 형식으로, 아래는 내 맘대로 풀었을 때 걸리는 시간이다.

확실히 dp로 풀어야 하는 문제는 dp로 풀어야한다... 시간 차이가 엄청 난다.

 

<내 맘대로 푼 경우>

 

#include <iostream>

 

using namespace std;

 

int arr[301][301];

int N, M, K;

int i, j, x, y;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cin >> N >> M;

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

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

            cin >> arr[z][j];

 

    cin >> K;

    for (int z = 1; z <= K; z++)

    {

        int sum = 0;

        cin >> i >> j >> x >> y;

        if (i != x)

        {

            for (int a = i; a <= x; a++)

                for (int b = j; b <= y; b++)

                    sum += arr[a][b];

        }

        else

        {

            for (int b = j; b <= y; b++)

                sum += arr[i][b];

        }

        cout << sum << "\n";

    }

}

 

 

<dp의 memorization 활용>

 

#include <iostream>

 

using namespace std;

 

int cache[301][301];

int N, M, K;

int i, j, x, y;

 

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    cin >> N >> M;

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

    {

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

        {

            int num;

            cin >> num;

            cache[a][b] = cache[a - 1][b] + cache[a][b - 1] - cache[a - 1][b - 1] + num;

        }

    }

    cin >> K;

 

    for (int testcase = 1; testcase <= K; testcase++)

    {

        cin >> i >> j >> x >> y;

        int sum = 0;

        sum = cache[x][y] - cache[i - 1][y] - cache[x][j - 1] + cache[i - 1][j - 1];

        cout << sum << "\n";

    }

}

cache[a][b] = cache[a - 1][b] + cache[a][b - 1] - cache[a - 1][b - 1] + num;

 

먼저 이 코드! 내가 만약 (1,1)~(x,y)까지의 합을 memorization으로 구한다고 한다면 이미 memorization이 진행된    (x-1,y)과 (x,y-1)을 더해주고 그곳에 (x,y)의 값 단 하나만을 더해주면 된다. (왼쪽 세로줄과 위쪽 가로줄을 더한다 생각!) 그렇게 되면 (x-1,y-1) 부분이 2번 더해지기 때문에 한번은 빼준다.

 

sum = cache[x][y] - cache[i - 1][y] - cache[x][j - 1] + cache[i - 1][j - 1]

 

하지만! 합의 시작이 (1,1)이 아닌 (i,j)이다. i의 왼쪽 세로줄과 j의 위쪽 가로줄을 빼주어야하는데 이때!!!!!!!! 그 범위는 x,y에 의해 결정될 것이다. 이때에도 (i-1,j-1)은 중복으로 빠지기 때문에 한번 더해줘야 한다.

 

https://lmcoa15.tistory.com/14 ==>이 블로그에 그림 설명이 잘 되어 있다.