초콜릿과 건포도

1. 후 2. 안타깝다 3. DP 어떻게 풀이하는지 조금 더 문제를 접해봐야함 4. 정의가  확실해야함 5. 인덱스와 값에 무엇이 들어가는지 그리고 어떻게 사용할지

#include<stdio.h> #include<iostream> using namespace std; typedef unsigned long long ll; #define N_MAX 5 int N, M, A[N_MAX][N_MAX], D[N_MAX][N_MAX][N_MAX][N_MAX], S[N_MAX][N_MAX], INF = (int)1e9; inline int g(int r1, int c1, int r2, int c2) { if (!r1 && !c1) return S[r2][c2]; if (!r1) return S[r2][c2] - S[r2][c1 - 1]; if (!c1) return S[r2][c2] - S[r1 - 1][c2]; return S[r2][c2] - S[r2][c1 - 1] - S[r1 - 1][c2] + S[r1 - 1][c1 - 1]; } int f(int r1, int c1, int r2, int c2) { if (r1 == r2 && c1 == c2) return 0; int &ret = D[r1][c1][r2][c2], ret2, sum; if (ret != -1) return ret; int i; ret = INF; sum = g(r1, c1, r2, c2); if (r1 < r2) { for (i = r1; i < r2; i++) { ret2 = f(r1, c1, i, c2) + f(i + 1, c1, r2, c2) + sum; if (ret > ret2) ret = ret2; } } if (c1 < c2) { for (i = c1; i < c2; i++) { ret2 = f(r1, c1, r2, i) + f(r1, i + 1, r2, c2) + sum; if (ret > ret2) ret = ret2; } } return ret; } int main() { freopen("input.txt", "r", stdin); int i, j, k, l, t, T; cin >> t; for (T = 1; T <= t; T++) { scanf("%d%d", &N, &M); for (i = 0; i < N; i++) for (j = 0; j < M; j++) scanf("%d", &A[i][j]); for (i = 0; i < N; i++) for (j = 0; j < M; j++) { for (k = i; k < N; k++) for (l = j; l < M; l++) { D[i][j][k][l] = -1; } } S[0][0] = A[0][0]; for (i = 1; i < N; i++) S[i][0] = S[i - 1][0] + A[i][0]; for (i = 1; i < M; i++) S[0][i] = S[0][i - 1] + A[0][i]; for (i = 1; i < N; i++) for (j = 1; j < M; j++) S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + A[i][j]; // 전체값 저장함 printf("#%d %d\n", T, f(0, 0, N - 1, M - 1)); } }