입력받은 숫자들을 2차원 int배열에 넣고
해당 배열을 사용하여 dp[i][j]의 값을 구한다.
dp[i][j-1] 와 dp[i-1][j] 의 값을 비교하여 dp[i][j]를 구한다.
만약 b[1][2]의 총 최대값을 구하려면 b[0][2]와 b[1][1] 을 비교하여 큰 값을 b[1][2]과 더하여 dp에 저장한다.
이것을 dp[N][M]까지 반복하여 계산하면 사탕수의 최대값을 구할 수 있다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class B11048 {
static int N,M;
static int[][] board;
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());
board = new int[N+1][M+1];
dp = new int[N+1][M+1];
for (int i = 1; i < N+1; i++) {
st = new StringTokenizer(br.readLine()," ");
for (int j = 1; j < M+1; j++) {
board[i][j] = Integer.parseInt(st.nextToken());
}
}
calc();
}
private static void calc() {
for (int i = 1; i < N+1; i++) {
for (int j = 1; j < M+1; j++) {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + board[i][j];
}
}
System.out.println(dp[N][M]);
}
}
'연습문제 > JAVA' 카테고리의 다른 글
[백준 java] 11053 - 가장 긴 증가하는 부분 수열 (0) | 2022.09.12 |
---|---|
[백준 java] 1890 - 점프 (0) | 2022.09.11 |
[백준 java] 10884 - 쉬운 계단 수 (0) | 2022.09.09 |
[백준 java] 11057 - 오르막 수 (0) | 2022.09.08 |
[백준 java] 11727 - 2xn 타일링 2 (0) | 2022.09.07 |