이코테 DP : 금광 [C++]

 

 

▶ 내 풀이

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int t, n, m;
const int MAX = 21;
int dp[MAX][MAX];


int main(void) {
	cin >> t;
	
	for (int i = 0; i < t; i++) {
		int max_gold = 0;
		
		cin >> n >> m;
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < m; k++) {
				int x = 0;
				cin >> x;
				dp[j][k] = x;
			}
		}

		// 두번째 열부터
		for (int y = 1; y < m; y++) {
			for (int x = 0; x < n; x++) {
				int max_num = 0;
				// 올수있는 세가지 경우중, 최댓값을 구한다. -> max_num
				if (x == 0) {
					max_num = max(dp[x][y - 1], dp[x+1][y - 1]);
				}else if (x == n - 1) {
					max_num = max(dp[x-1][y - 1], dp[x][y - 1]);
				}else {
					max_num = max(dp[x-1][y - 1], dp[x][y - 1], dp[x + 1][y - 1]);
				}
				
				// max_num과 현재의 값을 더한값을 현재값으로 갱신한다.
				dp[x][y] = max_num + dp[x][y];
				// 갱신된값이 그 전에 갱신된값들 보다 큰지아닌지 비교한다.
				max_gold = max(max_gold, dp[x][y]);
			}
		}
		
		cout << max_gold << '\n';
	}
}

 

▶ 다른 풀이

#include <bits/stdc++.h>

using namespace std;

int testCase, n, m;
int arr[20][20];
int dp[20][20];

int main(void) {
    // 테스트 케이스(Test Case) 입력
    cin >> testCase;
    for (int tc = 0; tc < testCase; tc++) {
        // 금광 정보 입력
        cin >> n >> m;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                cin >> arr[i][j];
            }
        }
        // 다이나믹 프로그래밍을 위한 2차원 DP 테이블 초기화
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i][j] = arr[i][j];
            }
        }
        // 다이나믹 프로그래밍 진행
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                int leftUp, leftDown, left;
                // 왼쪽 위에서 오는 경우
                if (i == 0) leftUp = 0;
                else leftUp = dp[i - 1][j - 1];
                // 왼쪽 아래에서 오는 경우
                if (i == n - 1) leftDown = 0;
                else leftDown = dp[i + 1][j - 1];
                // 왼쪽에서 오는 경우
                left = dp[i][j - 1];
                dp[i][j] = dp[i][j] + max(leftUp, max(leftDown, left));
            }
        }
        int result = 0;
        for (int i = 0; i < n; i++) {
            result = max(result, dp[i][m - 1]);
        }
        cout << result << '\n';
    }
}