백준(BOJ) 14916 거스름돈 C++ 풀이

문제 링크: https://www.acmicpc.net/problem/1749

1749번: 점수따먹기

문제 풀이에 이용된 알고리즘: 누적합, 다이나믹 프로그래밍

 

처음에는 만들 수 있는 모든 부분 행렬을 구하고, 각 부분 행렬 내 원소의 총 합 중 최대값을 구하는 방법에 대해서 생각해봤다.

 

부분 행렬을 결정하는 것은, 부분 행렬의 "좌측 상단"과 "우측 하단" 2가지 이다.

 

좌측 상단을 알고 있다면, 부분 행렬의 가로 길이와 세로 길이를 통해 우측 하단의 좌표를 구할 수 있다.

 

따라서 좌측 상단의 경우의 수(200x200)과 가로 길이 및 세로 길이 조합의 수(200x200)을 통해 부분 행렬의 개수가 구해지고, 부분 행렬 내 원소 합을 구하기 위해 돌게 되는 for문도 고려하면 시간 초과가 날 것이라고 예상 가능하다.

 

아래는 실제 시간 초과가 발생한 코드이다.

 

/* BOJ 1749 점수따먹기 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
#define endl '\n'
 
typedef long long ll;
 
int n, m, arr[201][201], answer;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> arr[i][j];
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) // (i, j)는 부분 행렬의 좌측 상단 좌표
            for (int h = 1; h <= n; h++)
                for (int w = 1; w <= m; w++) // h, w는 부분 행렬의 세로와 가로 길이
                {
                    int sum = 0; // 부분 행렬 내 원소 총합
                    for (int x = i; x < i + h; x++)
                        for (int y = j; y < j + w; y++) // (x, y)는 부분 행렬 내 원소
                            sum += arr[x][y];
 
                    answer = max(answer, sum); // 부분 행렬 내 원소의 총합 중 최대 값 찾기
                }
 
    cout << answer << endl;
 
    return 0;
}

 

따라서 누적합을 이용하여 해당 문제를 풀었다.

 

누적합을 저장하는 배열 prefix_sum에 대해서, prefix_sum[i][j]는 (1, 1) 지점부터 (i, j)까지의 직사각형 형태에 속하는 모든 원소들의 합을 정한 것이다.

 

이를 이용하면 (i1, j1) ~ (i2, j2)까지의 부분 행렬 내 원소의 합은 [i2][j2] - [i1-1][j2] - [i2][j1-1] + [i1-1][j1-1]로 비교적 빠르게 계산이 가능하다.

 

한 가지 주의할 점은, 최대값을 구하기 위해 answer를 단순 0으로 두고 max 함수를 적용하는 과정을 실행하면 안된다.

 

주어진 조건을 고려해보면 부분 행렬 내 원소의 합이 될 수 있는 가장 작은 수는 -10000 * 200 * 200이기 때문이다.

 

다만, answer를 -10000으로 두고 채점하여도, 맞았다고 뜨게 되는데 약간 데이터가 부족한 것으로 생각된다.

 

/* BOJ 1749 점수따먹기 */
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
#define endl '\n'
 
typedef long long ll;
 
int n, m, arr[201][201], prefix_sum[201][201];
int answer = -10000;
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m;
 
    int cur_row_sum = 0;
    for (int i = 1; i <= n; i++)
    {
        cur_row_sum = 0;
        for (int j = 1; j <= m; j++)
        {
            cin >> arr[i][j];
            cur_row_sum += arr[i][j];
            prefix_sum[i][j] = prefix_sum[i - 1][j] + cur_row_sum;
        }
    }
 
    for (int i1 = 1; i1 <= n; i1++)
        for (int j1 = 1; j1 <= m; j1++)
            for (int i2 = i1; i2 <= n; i2++)
                for (int j2 = j1; j2 <= m; j2++)
                    answer = max(answer,
                                 prefix_sum[i2][j2] - prefix_sum[i1 - 1][j2] - prefix_sum[i2][j1 - 1] + prefix_sum[i1 - 1][j1 - 1]);
 
    cout << answer << endl;
 
    return 0;
}