September 28, 2021

문제

NxM 크기의 금광이 있습니다. 금광은 1x1 크기의 칸으로 나누어져 있으며, 각 칸은 특정한 크기의 금이 들어있습니다.

채굴자느 첫 번째 열부터 출발하여 금을 캐기 시작합니다. 맨 처음에는 첫 번째 열의 어느 행에서든 출발할 수 있습니다. 이후에 m-1번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동해야 합니다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하는 프로그램을 작성하세요.

시간 제한

1초

메모리 제한

128MB

입력 조건

첫째 줄에 테스트 케이스 T가 입력됩니다.(1≤T≤1,000)

매 테스트 케이스 첫째 줄에 n과 m이 공백으로 구분되어 입력됩니다. (1≤n, m≤20)

둘째 줄에 nxm개의 위치에 매장된 금의 개수가 공백으로 구분되어 입력됩니다.(1≤각 위치에 매장된 금의 개수≤100)

출력 조건

테스트 케이스마다 채굴자가 얻을 수 있는 금의 최대 크기를 출력합니다. 각 테스트 케이스는 줄 바꿈을 이용해 구분합니다.

풀이

#include <stdio.h>

using namespace std;

int T, n[1000], m[1000], gold[1000][20][20], dp[1000][20][20], result[1000];
int dr[3] = {-1, 0, 1};

void getGold() {
    for (int i = 0; i < T; ++i) {
        for (int c = 0; c < m[i]; ++c) {
            for (int r = 0; r < n[i]; ++r) {
                if (c == 0) {
                    dp[i][r][c] = gold[i][r][c];
                } else {
                    for (int d = 0; d < 3; ++d) {
                        if (r + dr[d] >= 0 && r + dr[d] < n[i]) {
                            dp[i][r][c] = dp[i][r][c] > dp[i][r + dr[d]][c - 1] + gold[i][r][c] ? dp[i][r][c] : dp[i][r + dr[d]][c - 1] + gold[i][r][c];
                        }
                    }
                }
            }
        }

        for (int r = 0; r < n[i]; ++r) {
            result[i] = result[i] > dp[i][r][m[i] - 1] ? result[i] : dp[i][r][m[i] - 1];
        }
    }
}

int main() {
    scanf("%d", &T);

    for (int i = 0; i < T; ++i) {
        scanf("%d %d", &n[i], &m[i]);

        for (int r = 0; r < n[i]; ++r) {
            for (int c = 0; c < m[i]; ++c) {
                scanf("%d", &gold[i][r][c]);
            }
        }
    }

    getGold();

    for (int i = 0; i < T; ++i) {
        printf("%d\\n", result[i]);
    }

    return 0;
}