문제 설명
접근법
기본 형태
public static int DFS(int x, int y){
if(목적지 도착){
return ?;
}
if(dp에 값이 존재하면){
return dp[x][y]
}
dp[x][y] = ?;
for(int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if(조건을 만족하면){
dp[x][y] = Math.max(dp[x][y],DFS(nx,ny)로 계산한 다음값);
}
}
return dp[x][y];
}
정답
import java.util.*;
import java.io.*;
public class Main {
static int[] dx = { 0, 1, 0, -1 };
static int[] dy = { 1, 0, -1, 0 };
static int N, M;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
M = sc.nextInt();
int[][] board = new int[N][M];
int[][] dp = new int[N][M];
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1);
for (int j = 0; j < M; j++) {
board[i][j] = sc.nextInt();
}
}
DFS(0, 0, board, dp);
System.out.println(dp[0][0]);
}
public static int DFS(int x, int y, int[][] board, int[][] dp) {
if (x == N - 1 && y == M - 1) {
return 1;
}
if (dp[x][y] != -1) {
return dp[x][y];
}
dp[x][y] = 0;
for (int d = 0; d < 4; d++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (0 <= nx && nx < N && 0 <= ny && ny < M && board[x][y] > board[nx][ny]) {
dp[x][y] = Math.max(dp[x][y], dp[x][y] + DFS(nx, ny, board, dp));
}
}
return dp[x][y];
}
}
비슷한 문제
욕심쟁이 판다 | 풀이