Dynamic Programming q1

금광 캐기 문제

Question

nXm 크기의 금광이 있다. 각 칸 마다 금이 있으며 시작은 첫번째 열에서 진행한다. 그후 오른쪽 위, 오른쪽, 오른쪽 아래 방향으로 이동하면서 칸을 이동할 수 있는데, 이때 마지막 열에 도닥했을 때, 가질 수있는 최대 금의 양을 구해라

Example

1	2	3	2
2	1	4	1
0	6	4	7

위와 같이 3X4 크기의 금광이 있을 때 취할 수 있는 금의 최대양은 (2,1) -> (3,2) -> (3,3) -> (3,4) 을 이동해서 19만큼의 금이 최대값이다.

Solution

여기서 찾을 수 있는 점화식은 아래와 같다. row,col이 있을때 해당 칸으로 오기 위해 거쳐야하는 이전의 칸은 upleft,left,downleft 중에 하나이다.

만약, row==0 이면 upleft는 0이다 만약, row==n이면 down=0이다.

upleft=F_row-1,col-1

left=F_row,col-1

downleft=F_row+1,col-1

F_row,col=max(upleft,left,downleft)으로 반복적으로 수행하면 되고 마지막 열에 대해 최대값을 구하면 된다.

result=max(F_row,n)이다.

Solution

def gold():
  for col in range(cols):
    for row in range(rows):
      upleft,left,downleft=gold[row-1][col-1],gold[row][col-1],gold[row+1][col-1]
      if row==0:
        upleft=0
      if row ==rows-1:
        downleft=0
      gold[row][cold]+=max(upleft,left,downleft)
  result=0

  for row in range(rows):
    result=max(result,gold[row][-1])
    
  return result
    
if __name__ == "__main__":
  rows,cols=map(int,input().split)
  graph=[list(map(int,input().split)) for _ in range(row)]

  print(gold())