195.金鉱

18520 ワード
アルゴリズム#アルゴリズム# テキストリンク
  • n × mサイズの金鉱があります.金鉱は1 × 1の大きさの格子に分けられ、各格子には特定の大きさの金がある.

  • 採掘者は第1列から金を洗い始めた.最初は最初の列のどの行からでも出発できます.

  • その後m回を経て、毎回右上、右下の3つの位置のうちの1つに移動します.

  • そのため、採掘者が得ることができる最大の金の大きさを出力するプログラムを作成します.
    • 3 x 4の大きさの金鉱が存在すると仮定した.

    一番左の位置は(1, 1)で、一番右の下の位置は(n, m)で、上の例では(2, 1) -> (3, 2) -> (3,3) -> (3, 4)の位置に移動して、合計19万千金を採掘することができます.このときの値は一番です.

  • 入力条件

  • 1行目の入力テストケースT.(1 ≤ T ≤ 100)

  • 各試験盤キャビネットの最初の行には、nとmがスペースで区切られて入力されます.(1 ≤ n, m ≤ 20)

  • 2行目に入力された金の数はn x m箇所で、スペースで区切られています.(0≦位置あたりの黄金数≦100)

  • しゅつりょくじょうけん

  • 各テストケースは、採掘者が得ることができる最大の金の大きさを出力します.
  • 各テストケースは改行で区切られています.

    • 1.動的プログラミング

    
for tc in range(int(input())):
  n, m = map(int,input().split())
  array = list(map(int, input().split()))

  dp = []
  index = 0
  for i in range(n):
    dp.append(array[index: index + m])
    index += m

  for j in range(1, m):
      for i in range(n):
        #왼쪽 위에서 오는 경우
        if i == 0:
          left_up = 0
        else:
          left_up = dp[i - 1][j - 1] 
        #왼쪽 아래에서 오는 경우
        if i == n - 1:
          left_down = 0
        else:
          left_down = dp[i + 1][j - 1]
        #왼쪽에서 오는 경우
        left = dp[i][j - 1]
        dp[i][j] = dp[i][j] + max(left_up, left_down, left)

  result = 0

  for i in range(n):
    result = max(result, dp[i][m - 1])

  print(result)

    2. C++

    
#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';
    }
}
    Java : Array
    life cycle