[백준][자바] 14430 - 자원캐기 - DP

📌 문제

백준 | 자원캐기 | SILVER 2 | DP

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

 

 

📌 문제 탐색하기

• 제한된 범위 내에서 자원을 탐색
• (1,1) 부터 (N,M)까지 자원을 탐색
• 오른쪽, 아래쪽으로 한칸 이동 가능
• (x,y)에 자원이 있는 경우에만 해당 자원을 채취 가능

 

• 입력 :
  • n (세로길이 = 행), m(가로길이 = 열)
  • n행 m열에 걸쳐 탐사영역
  • 자원 = 1, 땅 = 0
• 출력 : 탐색할 수 있는 자원의 최대 숫자를 구하기

 

 

 

📌 알고리즘

• N과 M이 최대 300이므로, 땅의 크기는 최대 90000까지 가능
• 만약, 완전탐색으로 접근할 경우, N,M까지 가는 경우 O(300^2) + 최대 가지의 수임
• DP를 통해서, 최대 광석의 개수를 계속해서 업데이트한다면?
• example) DP[i][j] =grid[i][j] + Math.max(DP[i][j-1], DP[i-1][j])

 

 

📌 코드 설계하기

1. n,m, grid 입력
2. dp 갱신 (DP[i][j] =grid[i][j] + Math.max(DP[i][j-1], DP[i-1][j]))

단, i-1과 j-1이 계산에 필요하므로 기존 n,m보단 +1씩 큰 배열을 만들어서 outOfRange 에러를 방지한다.

 

 

📌 정답 코드

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

public class Main {

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

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[][] grid = new int[n+1][m+1];
        int[][] dp = new int[n+1][m+1];

        for(int i = 1; i<=n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 1; j<=m; j++){
                grid[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for(int i = 1; i <= n; i++){
            for(int j = 1; j<=m; j++){
                dp[i][j] = grid[i][j] + Math.max(dp[i][j-1], dp[i-1][j]);
            }
        }

        System.out.println(dp[n][m]);
    }
}

 

이전에 프로그래머스에서도 이와 비슷한 문제를 풀었던 기억이 난다.

DP는 코드보단 알고리즘 생각에 대한 문제이니, 잘 복습해두자 !! 🍀🍀