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

https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr town이라는 딕셔너리를 정의하고, key에는 각 위치의 좌표, value에는 각 위치에 도달하기까지 가능한 모든 경우의 수를 저장했습니다. 오른쪽과 아래쪽으로만 움직일 수 있기 때문에 현재 위치의 왼쪽과 위쪽의 값을 더해 현재 위치의 값을 갱신했습니다. 이때 왼쪽이나 위쪽에 길이 없어 index Error가 날 수 있는 곳은 길이 없는 곳은 제외하고..