[BOJ / python] 14430번: 자원 캐기

https://www.acmicpc.net/problem/14430

14430번: 자원 캐기

 

문제

 

풀이

첫번째 줄에서 얻은 값들을 n이라는 리스트에 저장하고, 두번째 줄부터 입력되는 탐사 영역의 각 구간들을 source라는 2차원 리스트를 생성하여 값을 저장한다. 동시에 각 구간에서의 최댓값을 저장할 result라는 2차원 배열을 source와 같은 크기로 생성한다. wook는 오른쪽이나 아래쪽으로 한 칸씩만 이동하기 때문에 바로 전에 다녀온 길은 위쪽이나 왼쪽에서의 한 칸이다. 가장 많은 자원을 캐는 길을 찾아야 하기 때문에 위쪽 한 칸과 왼쪽 한 칸 중 값이 더 커다란 방향의 값을 가져온 뒤, 현재 구간의 자원 개수를 그 최댓값에 더해준다. 이를 문제에 나와 있는 예제를 통해 표현해보면 아래와 같다.

왼쪽은 자원의 위치가 나타나있는 영역이고, 오른쪽은 그 영역에 대해 최댓값을 찾은 결과이다. 예제 출력 결과와 마찬가지로, 오른쪽 표의 오른쪽 아래의 숫자는 4로 나타난다. 이 방식을 그대로 코드에 적용시킨다면 아래와 같다.

 

코드

n=[*map(int,input().split())]
result=[[0 for i in range(n[1])] for i in range(n[0])]
source=[]
for i in range(n[0]):
  source.append([*map(int,input().split())])
for i in range(n[0]):
  for j in range(n[1]):
    if i==0 and j==0:
      result[i][j]=source[i][j]
    elif i==0 and j!=0:
      result[i][j]=source[i][j]+result[i][j-1]
    elif i!=0 and j==0:
      result[i][j]=source[i][j]+result[i-1][j]
    else:
      result[i][j]=source[i][j]+max(result[i-1][j],result[i][j-1])
print(result[n[0]-1][n[1]-1])

 

결과