[python] 이코테 - 금광

출처 : 이것이 취업을 위한 코딩테스트다 with Python

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

 

먼저, 생각해야 할 부분

 

1. DP 유형에서 핵심은 현재 -> 다음이 아니라, 이전 -> 현재이다.

     다시 말해, 내가 현재 상태에 있을 때 이전에 내가 있을 수 있는 곳들의 후보를 찾는 것이 핵심이다.

 

     문제에서 나는 현재 위치에서 우상, 우, 우하로 이동할 수 있다고 적혀있지만,

     점화식을 추론하기 위해서는 현재 위치일 때, 이전에 내가 있을 수 있는 곳을 추론해야한다.

     이 경우, 좌상, 좌, 좌하에서 현재 나의 위치로 올 수 있으므로 점화식은 아래와 같다.

 

gold[i][j] = gold[i][j] + max(gold[i-1][j-1], gold[i][j-1], gold[i+1][j-1])

 

---

풀이

 

def solution(n, m, miro):
    for c in range(1, m):
        for r in range(n):
            comp_list = []

            # 좌상
            if 0 <= r-1 < n and 0 <= c-1 < m:
                comp_list.append(miro[r-1][c-1])
            # 좌
            if 0 <= r < n and 0 <= c-1 < m:
                comp_list.append(miro[r][c-1])
            # 좌하
            if 0 <= r+1 < n and 0 <= c-1 < m:
                comp_list.append(miro[r+1][c-1])

            miro[r][c] += max(comp_list)

    # 마지막 열의 최댓값
    return max([row for row in zip(*miro)][m-1])

T = int(input())

for _ in range(T):
    n, m = map(int, input().split())
    miro_line = list(map(int, input().split()))
    miro = []

    for i in range(n):
        start = i * m
        end = i * m + m
        miro.append(miro_line[start:end])

    print(solution(n, m, miro))

 

---