[문제해결을 위한 창의적 알고리즘] 광석 수집 (고급 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

문제해결을 위한 창의적 알고리즘 목록