[백준] 14430번 - 자원 캐기 java

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

 

난이도 : S2

Tag : DP

풀이 일자 : 2025-03-08

---

문제 탐색하기

N: 탐사할 영역의 세로길이 (1 <=N <=300)

M: 탐사할 영역의 가로길이 (1 <=M <=300)

1: 자원

0: 빈 땅

 

로봇은 왼쪽 위(1, 1)부터 오른쪽 아래(N, M)까지 자원을 채집

이동 가능 방향: 오른쪽 또는 아래쪽

즉, N*M의 땅에서 로봇이 이동하며 모을 수 있는 자원의 최대 개수를 구하면 됩니다.

가능한 시간복잡도

완전탐색:

각 위치에서 왼쪽 또는 오른쪽으로 이동 가능하므로 대략 O(2^(N*M))입니다. 

최대 시간복잡도를 생각하면 O(2^(300*300))이므로 탐색 불가능합니다.

 

DP:

각 위치에 왔을 때 최선의 값을 유지하며 이동시 시간복잡도가 O(N*M)입니다.

N*M ≤ 90,000이므로 충분히 문제를 해결 가능합니다.

알고리즘 선택

DP를 선택해 보겠습니다.

문제를 보면 모든 영역에서 오른쪽, 또는 아래로만 이동합니다.

 

그러므로 dp [y][x]를 해당 위치까지 도달했을 때 모을 수 있는 자원의 최대 개수로 정의합니다.

(y, x)에 도착하기 전에 가능한 경로는 두 가지입니다.

1. 위쪽에서 내려오는 경우 → dp[y-1][x]
2. 왼쪽에서 오는 경우 → dp[y][x-1]

따라서, 둘 중 더 많은 자원을 모은 경로를 선택하면 됩니다.

 

그렇다면 아래와 같은 점화식을 도출할 수 있습니다.

dp[y][x] = land[y][x] + Math.max(dp[y-1][x], dp[y][x-1])

 

기저사례

첫 번째 행과 첫 번째 열은 오직 한 방향으로만 이동 가능하므로, 아래와 같이 초기화합니다.

1. 첫 번째 열 (dp[y][0])
   • 위쪽에서만 내려올 수 있음
   • dp[y][0] = dp[y-1][0] + land[y][0]
2. 첫 번째 행 (dp[0][x])
   • 왼쪽에서만 이동 가능
   • dp[0][x] = dp[0][x-1] + land[0][x]

왜냐하면 위 두 경우는 계속 아래로 끝까지, 오른쪽으로 끝까지 이동하는 경우만 존재하기 때문입니다.

 

아래 예제를 예시로 든다면 :

5 4
0 1 0 0
0 0 1 0
1 1 0 0
1 0 1 0
1 1 0 0

 

dp[0][0] = 0   dp[0][1] = 1   dp[0][2] = 1   dp[0][3] = 1

dp[1][0] = 0

dp[2][0] = 1

dp[3][0] = 2

dp[4][0] = 3 로 세팅이 됩니다.

---

코드 설계하기

1. N, M 크기의 땅 정보를 입력받고, land[][] 배열을 초기화합니다.
2. 첫 번째 행(dp[0][x])과 첫 번째 열(dp[y][0])을 초기화합니다.
3. 점화식 dp[y][x] = land[y][x] + max(dp[y-1][x], dp[y][x-1])을 적용하여 dp[][]를 채웁니다.
4. dp[N-1][M-1] 값을 출력합니다.

---

정답코드

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

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 n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        
        int[][] land = new int[n][m];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<m; j++){
                land[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int[][] dp = new int[n][m];
        dp[0][0] = land[0][0];
        for(int i=1; i<n; i++) dp[i][0] = land[i][0] + dp[i-1][0];
        for(int j=1; j<m; j++) dp[0][j] = land[0][j] + dp[0][j-1];
        
        for(int i=1; i<n; i++){
            for(int j=1; j<m; j++){
                dp[i][j] = land[i][j] + Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        
        System.out.println(dp[n-1][m-1]);
    }
}