금광 코드 및 해설 (파이썬)

출처: 이것이 취업을 위한 코딩 테스트다 with 파이썬, Q 31, p 375 이전에 풀이한 등굣길 문제와 유사하게 다이나믹 프로그래밍(DP)을 사용해 풀이했습니다. 입력으로 받은 금광에서 1열의 값은 그대로 두고, 2열부터 마지막 열까지 다음을 반복합니다. 첫 행의 경우 현재 위치를 왼쪽, 왼쪽 아래에서부터 접근해올 수 있습니다. 왼쪽 위는 금광이 존재하지 않습니다. 마지막 행의 경우 현재 위치를 왼쪽, 왼쪽 위에서부터 접근해올 수 있습니다. 왼쪽 아래는 금광이 존재하지 않습니다. 중간 행의 경우 현재 위치를 왼쪽, 왼쪽 위, 왼쪽 아래 모두에서 접근해올 수 있습니다. 접근해올 수 있는 모든 값들 중 최댓값을 현재 금광에서 얻을 수 있는 값과 더해줍니다. 마지막으로 마지막 열의 모든 값들 중 최댓값을..

2021.07.26