알고리즘 :: 이것이 코딩 테스트다 :: DP :: Q31 :: 금광

Embedded June·2020년 9월 20일
0

알고리즘::동빈나책

목록 보기
12/23

문제

n X m 크기의 금광에서 채굴자는 첫 번쨰 열부터 출발해서 m번에 걸쳐서 매번 오른쪽 위, 오른쪽, 오른쪽 아래 3가지 중 하나의 위치로 이동한다. 결과적으로 채굴자가 얻을 수 있는 금의 최대 크기를 출력하시오.

문제접근

  • 3가지 이동방법을 각각 수행한 뒤 그 결과를 메모이제이션 한다.
    • 오른쪽 위 이동: (y, x) -> (y - 1, x + 1)
    • 오른쪽 이동: (y, x) -> (y, x + 1)
    • 오른쪽 아래 이동: (y, x) -> (y + 1, x + 1)
  • 모든 출발 후보 지점으로부터 DP를 수행한다.

코드

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

static int T, N, M, mine[20][20], memo[20][20];

int solve(int y, int x) {
    if (y < 0 || y >= N || x < 0 || x >= M) return 0;	// [기저]: 범위 초과
    if (memo[y][x] != 0) return memo[y][x];	// [기저]: 이미 메모이제이션 된 값.
	
    return memo[y][x] = mine[y][x] + max(max(solve(y - 1, x + 1), solve(y, x + 1)), solve(y + 1, x + 1));
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> T;
    while (T--) {
        memset(mine, 0, sizeof(mine));
        memset(memo, 0, sizeof(memo));
        cin >> N >> M;
        for (int y = 0; y < N; ++y)
            for (int x = 0; x < M; ++x)
                cin >> mine[y][x];
        
        int answer = 0;	// 모든 출발 지점으로부터 DP를 수행 후 최대값을 찾는다.
        for (int i = 0; i < N; ++i) answer = max(answer, solve(i, 0));
        cout << answer << '\n';
    }
}
profile
임베디드 시스템 공학자를 지망하는 컴퓨터공학+전자공학 복수전공 학부생입니다. 타인의 피드백을 수용하고 숙고하고 대응하며 자극과 반응 사이의 간격을 늘리며 스스로 반응을 컨트롤 할 수 있는 주도적인 사람이 되는 것이 저의 20대의 목표입니다.

0개의 댓글