[문제해결을 위한 창의적 알고리즘] 광석 수집 (고급 p.103)
이 문제는 동적계획법 (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까지 하도록 되어 있으나, 최소한의 메모리를 사용하려면 200이 더 좋을 것 같다
// 물론 이것 때문에 아래에서 up, left 변수를 처리해야 하는 번거로움은 생겼다.
public static int[][] arr=new int[200][200];
public static int[][] dt = new int[200][200];
public static int max(int a, int b){
return a > b ? a : b;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
arr[i][j]=sc.nextInt();
sc.close();
// dt의 위쪽 값과 왼쪽 값을 받아 비교해 보고 더 큰쪽을 택해, arr의 자기 위치 값과 계속 더한다
for (int i = 0; i < n; i++){
for (int j=0; j<m; j++){
int up =0;
int left=0;
if (i>0)
up = dt[i-1][j];
if (j>0)
left = dt[i][j-1];
dt[i][j]=max(up, left)+arr[i][j];
}
}
// 0부터 시작했으므로 n-1, m-1위치값이 답이 된다
System.out.println(dt[n-1][m-1]);
return;
}
}
Big O(n*m)
Github: https://github.com/nevermet/CreativeAlgorithmAdv/blob/master/Mining103.java