[14430] 자원 캐기

🔗 문제 링크

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

🔍 문제 설명

인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. WOOK은 한 번에 오른쪽 또는 아래쪽으로 한 칸 이동할 수 있으며, 그 외의 방향으로 움직이는 것은 불가능하다. WOOK은 자신이 위치한 (x, y)에 자원이 있는 경우에만 해당 자원을 채취할 수 있다. WOOK이 탐사할 영역에 대한 정보가 주어질 때, WOOK이 탐색할 수 있는 자원의 최대 숫자를 구해라!

⚠️ 제한사항

• 첫째 줄에 WOOK이 탐사할 영역의 세로길이 N(1≤N≤300)과 가로길이 M(1≤M≤300)이 주어진다.

• 그 다음 N행 M열에 걸쳐 탐사영역에 대한 정보가 주어진다.

• 숫자는 공백으로 구분된다. (자원은 1, 빈 땅은 0으로 표시된다)

🗝 풀이 (언어 : Java)

DP로 푸는 문제이다. 오른쪽과 아래쪽만 이동할 수 있으므로, (0,0) 부터 차례대로 탐색한다.
현재 위치의 자원의 개수 + (왼쪽과 위쪽의 자원 개수 중에 최대 자원 개수)를 더해주면서 오른쪽 끝까지 간다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    private static final int[][] dir = {{0, -1}, {-1, 0}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int row = Integer.parseInt(st.nextToken());
        int column = Integer.parseInt(st.nextToken());
        int[][] matrix = new int[row][column];
        for (int i = 0; i < row; i++) {
            StringTokenizer st2 = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < column; j++) {
                matrix[i][j] = Integer.parseInt(st2.nextToken());
            }
        }
        System.out.println(countStone(matrix));
    }

    public static int countStone(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                //좌
                int dx1 = i + dir[0][0];
                int dy1 = j + dir[0][1];
                int case1 = (dx1 < 0 || dx1 >= matrix.length
                    || dy1 < 0 || dy1 >= matrix[0].length) ? 0 : matrix[dx1][dy1];
                //상
                int dx2 = i + dir[1][0];
                int dy2 = j + dir[1][1];
                int case2 = (dx2 < 0 || dx2 >= matrix.length
                    || dy2 < 0 || dy2 >= matrix[0].length) ? 0 : matrix[dx2][dy2];
                matrix[i][j] += Math.max(case1, case2);
            }
        }
        return matrix[matrix.length - 1][matrix[0].length - 1];
    }

}