광석 수집
-
[문제해결을 위한 창의적 알고리즘] 광석 수집 (고급 p.103)알고리즘 2017. 1. 27. 21:00
이 문제는 동적계획법 (Dynamic Programming)을 배울때, 가장 기본적인 유형으로 볼 수 있는 문제이다. 오른쪽과 아래쪽으로만으로 움직일 수 있다는 제약 조건 때문에, 왼쪽의 값과 위쪽의 값을 비교해 가면서 다이내믹 테이블을 업데이트하면서 답을 구해갈 수 있다. 나머지 설명은 책을 참고하면 되겠다. 책을 읽다 보니 한가지 수정했으면 하는 부분이 있는데 바로 106페이지의 T[i][j] 점화식에서 base case로 0 (i=0, j=0)이라고 되어 있는데, mine[0][0]으로 하는 것이 맞을 것 같다. import java.util.Scanner; public class Mining103 {public static int n;public static int m;// 책에서는 220까지 하..