[C++] BOJ(백준) 17498 폴짝 게임

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

17498번: 폴짝 게임

 

DP 문제다.

 

정적 할당을 하면 배열의 공간 낭비가 심할 것 같아 동적 할당을 했다.

(동적 해제는 까먹음)

 

입력으로 음수가 들어와 점수의 최대 값이 음수가 될 수 있으므로 dp의 초기값을 int 범위의 최솟값으로 지정했다.

 

지나온 길에서 거리가 d 이하면 점프가 가능하다. 고로 모든 경우의 수의 점프를 고려해야한다.

행을 움직이고 남은만큼 열을 움직일 수 있으므로 4중 포문을 이용했다.

 

마지막 줄에서 최댓값을 찾았다.

#include <iostream>
#include <limits>
using namespace std;

int main() {
	// 입출력 속도를 단축시키기 위함
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m, d;	cin >> n >> m >> d;

	// 2차원 배열 동적 할당
	int** arr = new int* [n];
	int** dp = new int* [n];
	for (int i = 0; i < n; i++) {
		arr[i] = new int[m];
		dp[i] = new int[m];
	}

	// 배열 초기화
	fill(dp[0], dp[0] + m, 0);
	for (int i = 1; i < n; i++) fill(dp[i], dp[i] + m, numeric_limits<int>::min());

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

	// 지나온 길로부터 폴짝
	for (int i = 1; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 1; k <= d; k++) {
				for (int l = 1; l <= k; l++) {
					int r = i - l;
					int c1 = j - (k - l);
					int c2 = j + (k - l);

					if (r < 0) continue;

					if (c1 >= 0) dp[i][j] = max(dp[i][j], dp[r][c1] + arr[r][c1] * arr[i][j]);
					if (c2 < m) dp[i][j] = max(dp[i][j], dp[r][c2] + arr[r][c2] * arr[i][j]);
				}
			}
		}
	}

	// 마지막 줄 중 최댓값
	int re = numeric_limits<int>::min();
	for (int i = 0; i < m; i++)
		re = max(re, dp[n - 1][i]);

	cout << re;
}

o(*^＠^*)o