[백준 17498번] 폴짝 게임 / C++

문제

태균이는 분필과 바닥만 있으면 언제든지 할 수 있는 재미있는 게임을 하나 만들었습니다.

바닥에 N×M 사각 격자를 그린 뒤 각 칸에 정수들을 쓰고 다음의 규칙을 따라 게임을 진행합니다.

• 1번 행에 있는 원하는 칸을 하나 정하여 해당 칸에서 시작합니다.
• N번 행에 있는 임의의 칸에 도착하면 게임이 끝납니다.
• 칸에서 칸으로 이동하려면 행의 번호가 증가하는 칸으로만 이동이 가능하며 칸 사이의 거리가 D이하여야 합니다. 즉, R행 C열에서 P행 Q열로 이동하려면 P > R 이며 | P - R | + | Q - C | ≤ D 를 만족해야 합니다.
• 게임 시작 시 점수의 초기값은 0이며, 칸에서 칸으로 이동할 때 각 칸의 수를 곱하여 현재 점수에 더합니다.

칸에 적힌 수들이 주어지면 게임에서 낼 수 있는 최대 점수를 구해주세요.

입력

첫 번째 줄에 행의 개수 N과 열의 개수 M (2 ≤ N×M ≤ 200,000, 2 ≤ N) 그리고 최대 점프 거리 정수 D (1 ≤ D ≤ 10) 가 주어집니다.

i+1 번째 줄에는 i (1 ≤ i ≤ N) 번째 행에 있는 쓰여있는 정수 ai,1, ai,2, ..., ai,m (-100 ≤ ai,j ≤ 100) 이 순서대로 주어집니다.

출력

첫 번째 줄에 게임에서 낼 수 있는 최대 점수를 출력합니다.

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
#define INF 9999999999
typedef long long ll;

int N, M, D;
vector<vector<ll>> MAP;
vector<vector<ll>> dp;

void cal_dp(int x, int y) {
    //현재 칸에서 이동거리가 D이하인 칸으로 이동
	for (int i = x + 1; i <= x + D; i++) {
		for (int j = y - D + 1; j <= y + D - 1; j++) {
            //배열의 범위를 벗어나지 않고
			if (i >= 0 && i < N && j >= 0 && j < M) {
                //칸 사이의 이동거리가 D이하이면
				if (i - x + abs(y - j) <= D) {
                        //배열 값 갱신
						dp[i][j] = max(dp[i][j], dp[x][y] + (MAP[x][y] * MAP[i][j]));
				}
			}
		}
	}
}

int main() {
	ll answer = -INF;

	cin >> N >> M >> D;

	MAP.assign(N, vector<ll>(M));
    //DP배열은 -INF로 초기화 (점수가 음수일 수 있기 때문에)
	dp.assign(N, vector<ll>(M, -INF));

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> MAP[i][j];
		}
	}
    //첫번째행의 DP값은 0으로 초기화
	for (int i = 0; i < M; i++) {
		dp[0][i] = 0;
	}

	for (int i = 0; i < N - 1; i++) {
		for (int j = 0; j < M; j++) {
			cal_dp(i, j);
		}
	}

	for (int i = 0; i < M; i++) {
		answer = max(answer, dp[N - 1][i]);
	}

	cout << answer;
}