[백준/Java] 14430번 : 자원 캐기

✏️ 문제 탐색

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

 

NxM 행렬을 오른쪽, 아래쪽 방향으로만 탐색한다.

(0, 0)에서 (N-1, M-1)까지 탐색할 때, 최대한 많이 수집할 수 있는 광석(1)의 개수를 구하라.

 

✏️ 구현 아이디어

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

 

로봇이 이동하는 방향은 오른쪽, 아래 뿐이다.

그러므로 어떤 한 좌표에 로봇이 도달하려면 왼쪽 또는 위쪽에서 오는 경로밖에 없다.

 

따라서 어떤 좌표에 도달했을 때 '로봇이 최대로 얻을 수 있는 광석의 개수'는

(왼쪽 좌표가 최대로 가질 수 있는 광석의 개수, 위쪽 좌표가 최대로 가질 수 있는 광석의 개수 중 더 큰 값)

+ (현재 좌표에 있는 광석 개수)가 된다. 

 

즉 위 예시의 경우 각 좌표를 '로봇이 최대로 얻을 수 있는 광석의 개수'로 채우면 다음과 같다.

• (0, 0) : 광석이 없으므로 0
• (0, 1) : 로봇이 왼쪽에서 온 경우, 광석을 최대 0개 가지고 있음(0) + 현재 좌표에 광석이 있음(1) = 1
• (1, 1) : Max(로봇이 위쪽에서 온 경우, 광석을 최대 1개 가지고 있음(1), 로봇이 왼쪽에서 온 경우, 광석을 최대 0개 가지고 있음(0)) + 현재 좌표에 광석이 없음(0) = 1
• ...

점화식은 dp[x][y] = Max(dp[x-1][y], dp[x][y-1]) + dp[x][y] 로 도출된다.

✏️ 알고리즘

어떤 좌표가 가질 수 있는 최대 광석의 개수를 구할 때 왼쪽, 위쪽 좌표의 최대 광석 개수를 이용하여 구한다.

이전의 답을 기억했다가 다음 문제의 답을 구할 때 사용하므로, DP로 푸는 게 적절하다.

✏️ 시간 복잡도

DP는 모든 경우를 1번씩만 연산하므로 시간 복잡도가 O(N)이다.

N, M은 각각 최대 300개이므로 총 좌표의 수는 최대 90000개이다. 

따라서 제한 시간(2초) 안에 연산 가능하다.

✏️ 코드 설계

1. dp[][]에 값을 입력받음
2. 각 좌표에 대해 dp()함수 실행하여, 최대로 가질 수 있는 광석 개수를 저장함
   1. 왼쪽, 위 모두 좌표가 없다면 -(0, 0)을 의미- 그 값 그대로 유지
   2. 위쪽 좌표가 없다면 -0행- 왼쪽 좌표의 최대값 + 현재 좌표의 값
   3. 왼쪽 좌표가 없다면 -0열- 위쪽 좌표의 최대값 + 현재 좌표의 값
   4. 둘 다 있다면 Max(왼쪽, 위쪽 좌표 최대값) + 현재 좌표의 값
3. 맨 마지막 좌표가 가질 수 있는 광석 개수를 구해야 하므로, dp[N-1][M-1]에 저장된 값을 출력

✏️ 정답 코드

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

public class Main {
    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 = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        dp = new int[N][M];
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<M; j++){
                dp[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                dp(i, j);
            }
        }

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

    }
    static void dp(int x, int y){
        if(x==0 && y==0){
            //왼쪽, 위 모두 좌표가 없음
            return;
        }else if(x<1 && y>0){
        	//위쪽 좌표가 없음
            dp[x][y] = dp[x][y-1] + dp[x][y];
        }else if(y<1 && x>0){
        	//왼쪽 좌표가 없음
            dp[x][y] = dp[x-1][y] + dp[x][y];
        }else{
            dp[x][y] = Math.max(dp[x-1][y], dp[x][y-1]) + dp[x][y];
        }

    }

}