더블릿_scv자원채취

동적계획법 다이나믹프로그래밍을 사용하여 풀 수 있는 문제이다. 

맨 처음은 완전탐색의 방법을 사용하였으나 테스트케이스 9개? 정도 맞추고 시간초과났다.

다이나믹프로그래밍을 쉽게 적용하여 풀 수 있는 문제라는 생각을 해보았다.

점화식은 간단하다.

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j]로써

입력받은 배열을 arr로 놓았고 dp라는 배열을 만들어서 현재까지 지나오면서 채취할 수 있는 자원의 최대양을 저장하는 배열을 하나 더 만들었다. 

for문을 돌면서 현재의 위치에서 경로 중 가장 자원을 많이 채취 할 수 있는 양을 계산해주었다.(이게 가능한 것은 scv가 오른쪽 또는 아래쪽으로만 이동 할 수 있기 때문이다.)

현재의 배열의 위치는 왼쪽에서 진입하는 scv가 채취하는 최대의 양 또는 위쪽에서 진입하는 scv가 채취하는 최대의양을 말한다.