다이나믹 프로그래밍 - 1. 금광 (Flipkart 인터뷰 기출)

문제

구현코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int cnt = 0;
		StringTokenizer st;
		while(cnt < n){
			st = new StringTokenizer(br.readLine());
			int row = Integer.parseInt(st.nextToken());
			int col = Integer.parseInt(st.nextToken());
			int[][] arr = new int[row][col];
			int[][] dp = new int[row][col];
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < row; i++){
				for(int j = 0; j < col; j++){
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			for(int i = 0; i < row ; i++){
				dp[i][0] = arr[i][0];
			}
			for(int j = 1; j < col; j++){
				for(int i = 0 ; i < row; i++){
					int leftDown, left, leftUp;
					if(i == 0) leftUp = 0;
					else leftUp = dp[i - 1][j - 1];
					left = dp[i][j - 1]; 
					if(i == row - 1)  leftDown = 0;
					else leftDown = dp[i + 1][j -1];
					dp[i][j] = arr[i][j] + Math.max(leftDown, Math.max(left, leftUp));
				}
			}
			int result = 0;
			for(int i = 0 ; i < row ; i++){
				result = Math.max(result, dp[i][col - 1]);
			}
			System.out.println(result);
			cnt++;
		}

		
	}

}

코드해석

다이나믹 프로그래밍 문제는 코딩테스트에서 엄청 어려운 문제로는 나오지 않는다고 한다. 즉 점화식만 잘 세우면 되는 것이다. 문제를 보면, 금을 체굴하는데 총 합이 가장 크도록 해야한다.
또한 왼쪽에서부터 시작하여 오른쪽으로 이동하는데 이동할때 오른쪽 위, 오른쪽, 오른쪽 아래 세가지 방법으로만 움직일 수 있다.
그렇다는건 dp 배열을 만들어서 첫번째 행값을 먼저 저장시켜 둔 후에 두번째 행부터 마지막행까지
dp[i][j] = arr[i][j] + Math.max(leftDown, Math.max(left, leftUp)); 이러한 점화식이 세워진다. 문론 예외도 있다. 만약 맨위칸이던가 맨아래칸이라면 예외를 시켜준다.
그 후에 마지막 행에서 가장 큰 값을 골라주면 되는문제이다.