백준 17498 (C++) 폴짝 게임

 

이해

입력 D의 범위 안에서 최대 점수('현재 점수 * 다음 점수'의 합)을 구한다.

 

입력받은 2차원 배열과 같은 크기의 dp[i][j]를 만들자.

dp[i][j]가 i행 j열 까지의 최대 점수라고 할 때,

 

dp[i][j]는 i행 j열로 가기 전 단계 x행 y열에서,

'x행 y열의 점수 * i행 j열의 점수' 연산을 더하는 값과, 더하지 않는 값 중의 최댓값이다.

 

따라서

 

dp[i][j] = max(dp[i][j], dp[x][y] + cur*next);

 

라는 점화식을 떠올리는 것은 쉽다.

 

 

 

틀렸습니다

70%쯔음에서 '틀렸습니다'를 받았다면
INF(dp배열 또는 답의 초기값의 최저)의 값을 너무 낮게 설정했을 수 있다.

메모리 초과가 났다면 입력의 2차원 배열을 int arr[100001][100001]로 잡는 것을 포기하자!

 

 

때문에 나는 n,m을 입력 받은 후 vector의 크기를 초기화했다.

또 vector나 arr의 type을 ll(= long long) 으로 해보자.

 

 

 

 

 

---

코드

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>
using namespace std;
using ll = long long;
const int MAX = 10001;
const ll INF = 9999987654321;
ll n,m,d,ans = -INF;
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> d;
    vector<vector<ll> > arr(n, vector<ll>(m,0));
    vector<vector<ll> > dp(n, vector<ll>(m,0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            dp[i][j] = -INF;
        }
    }
    for (int j = 0; j < m; j++) dp[0][j] = 0;
    
    for (int x = 0; x < n; x++) {
        for (int y = 0; y < m; y++) {
            for (int i = x + 1; i <= x + d; i++) {
                for (int j = y - d; j <= y + d; j++) {
                    if (j < 0 || i >= n || j >= m) continue;
                    int cur = arr[x][y];
                    int next = arr[i][j];
                    if (abs(i - x) + abs(j - y) <= d) {
                        dp[i][j] = max(dp[i][j], dp[x][y] + cur*next);
                    }
                }
            }
        }
    }
    for (int j = 0; j < m; j++) {
        ans = max(ans, dp[n-1][j]);
    }
    cout << ans;
    return 0;
}

 

 

 

 

---

 

시행착오

탐색의 범위를 x, y로 잡았는데 이렇게 적고보니 오른쪽 아래로밖에 탐색할 수 없었다.

 

 

    for (int x = 1; x <= d; x++) {
        int y = d-x;
        for (int i = 0; i < n-x+1; i++) {
            for (int j = 0; j < m-y; j++) {
                int cur = arr[i][j];
                int next = arr[i+x][j+y];
                dp[i+x][j+y] = max(dp[i+x][j+y], + dp[i][j] + cur * next);
            }
        }
    }