[C++] BOJ 1749번 : 점수따먹기

 

 

https://www.acmicpc.net/problem/1749

 

문제 3줄 요약

1. 동주와 점수 따먹기 게임을 한다.

2. N*M 행렬 각 칸에 -10'000 ~ 10'000의 정수를 하나씩 쓴다.

3. 행렬의 부분 행렬의 합이 최대가 되게 구하라!

 

---

 

 

예제를 보고

누적합을 생각하니 DP를 사용해야겠는데?

라는 생각이 떠올랐고

풀었던 유사한 문제가 생각났다.

 

 

https://59travel.tistory.com/104

[C++] BOJ 15724번 : 주지수

 

바로

주지수 문제!!

 

해당 문제에서 또한 2차원 배열의 부분 행렬 합을 구하는 문제였다.

위에서 DP를 왜 사용해야하는지

그림을 통해 자세히 설명해놨으니 한번 살펴보는 것을 추천한다!!

 

---

 

먼저

누적합에 대한 DP 테이블부터 작성해주었다.

 

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(i > 0) game[i][j] += game[i-1][j];
            if(j > 0) game[i][j] += game[i][j-1];
            if(i>0 && j>0) game[i][j] -= game[i-1][j-1];
        }
    }

 

 

(1, 1)부터 시작하여 (i, j) 까지의 점수를

DP 테이블에 채워준다.

 

테이블 값을 이용하여

(1, 1) ~ (i, j) 까지의 점수가 아닌

모든 부분 행렬을 브루트 포스 알고리즘을 통하여 살펴볼 것이다.

 

---

 

    long long value = -10000;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            value = max(value, game[i][j]);

            long long cal_value = 0;
            for(int rec_i = 0; rec_i<=i; rec_i++)
            {
                for(int rec_j = 0; rec_j<=j; rec_j++)
                {
                    cal_value = game[i][j];
                    if(rec_j>0) cal_value -= game[i][rec_j-1];
                    if(rec_i>0) cal_value -= game[rec_i-1][j];
                    if(rec_i > 0 && rec_j > 0) cal_value += game[rec_i-1][rec_j-1];

                    value = max(value, cal_value);
                    cal_value = 0;
                }
            }
        }
    }

 

(i, j) 좌표를 설정해두고

(1, 1) ~ (i, j) 사이의 생기는 부분 행렬(rec_i, rec_j)을 탐색한다.

 

부분 행렬의 점수 값이

지금까지의 최대 값보다 크다면 갱신해준다.

 

따라서

아래와 같이 작성할 수 있겠다!

 

#include <iostream>

using namespace std;

long long game[201][201];

int main(void){
    ios::sync_with_stdio(0); // c stream, c++ stream 중 c++ stream만 사용
    cin.tie(0); // 버퍼 비우지 않음

    long long n, m;
    cin >> n >> m;

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
            cin >> game[i][j];
    }

    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            if(i > 0) game[i][j] += game[i-1][j];
            if(j > 0) game[i][j] += game[i][j-1];
            if(i>0 && j>0) game[i][j] -= game[i-1][j-1];
        }
    }

    long long value = -10000;
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<m; j++)
        {
            value = max(value, game[i][j]);

            long long cal_value = 0;
            for(int rec_i = 0; rec_i<=i; rec_i++)
            {
                for(int rec_j = 0; rec_j<=j; rec_j++)
                {
                    cal_value = game[i][j];
                    if(rec_j>0) cal_value -= game[i][rec_j-1];
                    if(rec_i>0) cal_value -= game[rec_i-1][j];
                    if(rec_i > 0 && rec_j > 0) cal_value += game[rec_i-1][rec_j-1];

                    value = max(value, cal_value);
                    cal_value = 0;
                }
            }
        }
    }
    cout << value;
    return 0;
}

 

---

 

DP는 어느 카테고리든 참 많이 사용되는 것 같다..

 

끝!