[백준, 자바] 11048번 - 이동하기

문제 링크
https://www.acmicpc.net/problem/11048

최종 코드(정답)

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int height = Integer.parseInt(st.nextToken());
        int width = Integer.parseInt(st.nextToken());

        int[][] dp = new int[height + 1][width + 1];

        for (int i = 1; i <= height; i++) {
            StringTokenizer candies = new StringTokenizer(br.readLine());
            for (int j = 1; j <= width; j++) {
                int candy = Integer.parseInt(candies.nextToken());
                int fromLeft = dp[i][j - 1];
                int fromUp = dp[i - 1][j];
                int fromDiagonal = dp[i - 1][j - 1];

                dp[i][j] = Math.max(fromLeft, Math.max(fromUp, fromDiagonal)) + candy;
            }
        }
        System.out.println(dp[height][width]);
    }
}

풀이
개인적으로 동적 프로그래밍은 처음 진입하기가 너무 어려운 알고리즘이었다.
일단 유명한 나동빈님의 파이썬 알고리즘 책을 사서 보기도 했는데, 그 책의 경우 맨 왼쪽 세로줄을 초기화한 상태로 연산을 들어가더라고.

실제 주어진 세로 가로값보다 + 1인 배열을 선언하고
1부터 연산을 시작하면 실제로 위 그림처럼 1줄이 가로세로로 빈다.
그러면 제일 위 숫자가 -1을 해도 indexOutof~ 예외가 발생하지 않는다.

좀 무식하지만 [][]식으로 -1하고 하는게 헷갈려서
변수로 일일이 할당하면서 했다.
더 풀어봐야 이해할 거 같다.