[백준 자바 11048] 이동하기 (실버2)

 

https://www.acmicpc.net/problem/11048

 

 

설명

전형적인 DP 문제이다. 문제에서는 (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있다는 부분 때문에 현재 위치를 기준으로 다음 위치의 값을 어떻게 넣어줄지 생각하게 되는데, DP는 역으로 현재 위치의 값이 과거의 어느 위치로부터 영향받았는지로 생각하면 조금 더 수월하게 풀린다. 물론 그래도 DP는 너무 어렵다.,...

 

문제의 답이 N, M에 도착할 때 가장 많은 사탕을 가지고 있어야 하는 경우이고, 이동은 오른쪽, 아래, 오른쪽 아래 대각선 3방향으로 밖에 이동하지 못한다는 조건으로 생각해 보자. 

 

두 번째 조건을 반대로 생각해보면, 현재 위치에 있으려면 그전에는 왼쪽, 위, 왼쪽 위 대각선 중 하나에 있어야 한다. 

 

여기서 첫 번째 조건을 생각해보면, 최대한 많은 사탕을 가지고 있으려면 왼쪽, 위, 대각선 중 가장 많은 사탕을 가지고 있는 경우에 현재 위치의 사탕값을 더하면 된다. 

 

현재 위치 사탕 최댓값 = 현재 위치 사탕 개수 + Max(왼쪽 사탕 개수, 위쪽 사탕 개수, 왼쪽 위 사탕 개수)

 

이를 수식으로 표현하면 위와 같다. 

 

또 꽤 많은 DP 문제를 풀 때, N개의 요소가 있다면 배열을 N+1 크기로 만들어서 0번째 인덱스를 0으로 초기화해두면 코드가 더욱 간결해진다. 

 

전체 코드

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

public class Main {

    static int stoi(String s) {
        return Integer.parseInt(s);
    }

    static int N, M;
    static int[][] dp;

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

        N = stoi(st.nextToken());
        M = stoi(st.nextToken());

        dp = new int[N + 1][M + 1]; // (1)

        // (2)
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= M; j++) {
                dp[i][j] = Math.max(dp[i][j - 1], Math.max(dp[i - 1][j], dp[i - 1][j - 1])) + stoi(st.nextToken());
            }
        }

        System.out.println(dp[N][M]);
    }
}

타 풀이에서는 2차원 배열을 2개 선언해서 하나는 입력용, 하나는 DP용으로 푸는 경우가 많았는데, 문제 특성상 왼쪽 위부터 오른쪽 아래까지 오른쪽으로 돌면서 차례차례 계산해 나가기 때문에 2차원 배열 하나만 써도 풀린다. 

 

(1) 부분

위의 팁 부분에서 말한 것처럼, N, M 각각에 +1씩 해주어서 i = 0, j = 0 인 부분을 0으로 기본값 초기화를 해두었다. 

 

(2) 부분

우선 i, j가 1부터 시작한다. 

그리고 첫 행(가로줄)을 StringTokenizer로 입력받고, 각 열(세로줄)마다 정수로 변환한 뒤, [i][j - 1], [i - 1][j], [i - 1][j - 1] 이렇게 왼쪽, 위쪽, 왼쪽 위 대각선의 값 중 최댓값을 가져와서, 이를 입력값(현재 위치의 사탕 개수)과 더하여 2차원 배열에 넣어준다. 

 

i - 1 이나 j - 1을 해도 문제가 없는 이유는 i, j 가 1부터 시작해서이고, 각 0번째 인덱스는 0으로 초기화되기 때문에 계산에 문제가 생기지 않는다.