자원 채취

문제

N x M의 지도가 주어지며, 이 지도의 각 칸에는 자원이 존재한다. 자원의 양은 정수로 나타난다. 다음 그림은 5 x 6 의 지도에 존재하는 자원을 나타낸다.

철수는 자원을 채취하는 로봇을 갖고 있으며, 이 로봇은 (0, 0) 에서 출발하여 (N-1, M-1) 에서 자원 채취를 마친다. 로봇은 한가지 제약이 있는데, 오른쪽과 아랫쪽으로밖에 움직일 수 없다는 것이다. 이 로봇을 이용하여 가장 많이 채취할 수 있는 자원의 양을 출력하는 프로그램을 작성하시오. 위의 예제의 경우 다음과 같이 채취하는 것이 최대이며, 그 양은 49이다.

 

입력

첫 번째 줄에 N, M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 두 번째 줄부터 N x M 의 지도에 존재하는 자원의 양이 주어진다.

 

출력

로봇을 이용하여 채취할 수 있는 자원의 양의 최댓값을 출력한다.

 

예제 입력

5 6

1 7 3 2 8 0

9 2 3 4 5 4

3 4 7 8 2 2

1 4 3 1 4 1

3 2 5 5 3 8

예제 출력

49

 

# 접근법

0	0	0	0	0	0	0
0	1	7	3	2	8	0
0	9	2	3	4	5	4
0	3	4	7	8	2	2
0	1	4	3	1	4	1
0	3	2	5	5	3	8

우선 위쪽과 좌측에 왜 0이 생겼는지 알기전에

맨 처음 위치에 있는 1의 값이 어떻게 나왔을 지를 생각해보자.

문제 조건에서 "한가지 제약이 있는데, 오른쪽과 아랫쪽으로밖에 움직일 수 없다는 것"이라는 사항이 주어진다.

 

1이라는 요소는 이전 0요소의 오른쪽값과 아래쪽 값 중 더 큰 값이 더해진값이다.

이 논리로 dp_table을 완성시켜보면

그 옆 7이라는 요소의 위치의 최댓값은 그위의 값(0)과 좌측의 값(1) 중의 더 큰 값인 1과 자기자신의 값이 7이 더해진 8이된다.

 

1아래 9를 보자 9위치의 최댓값은 위의 값인(1)과 좌측의 값(0) 중 큰 값인 1 + 9(자기자신) = 10이 된다. 

아래의 dp_table의 값을 모두 채우지는 않겠다.

 

[dp_table]

0	0	0	0	0	0	0
0	1	8
0	10
0
0
0						49

 

이런 패턴으로 점화식을 만들면 아래와 같이 나오게 된다.

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

결국 이렇게 채워가면 마지막에 우리가 원하는 답이 들어있다.

 

#코드

import sys
 
 
if __name__ == "__main__":
  input = sys.stdin.readline
  
  n, m     = map(int, input().split())
  getArr   = [list(map(int, input().split())) for _ in range(n)]
  dp_table = [[0]*(m+1) for _ in range(n+1)] 
  
  for i in range(1, n+1):  
    for j in range(1, m+1):
      dp_table[i][j] = max(dp_table[i-1][j], dp_table[i][j-1]) + getArr[i-1][j-1] 
   
   
  print(dp_table[n][m])