금광

문제

금광은 N,M 행열로 구성되어 있다.

첫번째 열부터 시작해 마지막 열까지 이동하는데, 방문한 행에 있는 금을 캘 수 있다.

오른쪽 위, 아래, 옆 중 하나를 선택해 이동가능하다.

최대한 많이 캔경우 금의 양은?

 

 

유형 파악 및 구현

금광 (x, y)는 (x-1, y-1) or (x, y-1), (x+1, y-1) 중 하나와 더해 가장 크게 만들어야 한다.

첫번째 열부터 시작하니 이동 경로마다 값을 구하기 보단 생각을 역전해서

두번째 열에 있는 금들은 첫번째 열의 어떤 금들과 더해져야 가장 커지는가?에 대해서 생각하면 좋다.

 

1행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가?

2행 2열은 1열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가?

 

...

 

1행 4열은 3열의 금들 중 어떤 금이랑 합쳐져야 가장 커지는가?

 

이 후, 마지막 열에 금들 중 가장 큰 값을 출력한다.

 

또한, 전줄이 현재 처리하는 줄에 영향을 끼치므로 DP유형으로 볼 수 있다.

 

 

 

코드

t = int(input())
final_result = []
for i in range(t):
    n, m = map(int, input().split())
    test = list(map(int, input().split()))

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

    dx = [-1, 0, 1]
    max_value = 0

    while(1):
        result = 0
        for y in range(1, m):
            for x in range(n):
                max_value = 0
                for i in range(3):
                    before_x = x + dx[i]
                    before_y = y + -1
                    if before_x < 0 or before_x >= n or before_y < 0:
                        continue
                    max_value = max(max_value, graph[before_x][before_y])
                graph[x][y] = max_value + graph[x][y]
        for i in range(n):
            result = max(result, graph[i][m-1])
        final_result.append(result)
        break
print(final_result)