Create 1.py

ndb796 · web-flow · commit 7c2046b673e2 · 2020-06-24T11:09:45.000+09:00
diff --git a/16/1.py b/16/1.py
@@ -0,0 +1,35 @@
+# 테스트 케이스(Test Case) 입력
+for tc in range(int(input())):
+    # 금광 정보 입력
+    n, m = map(int, input().split())
+    data = list(map(int, input().split()))
+
+    # 다이나믹 프로그래밍을 위한 이차원 테이블 초기화
+    dp = []
+    index = 0
+    for i in range(n):
+        dp.append(data[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)
