백준 1937 욕심쟁이 판다 Java

 

정답률 29%인 dp 문제 욕심쟁이 판다 문제이다.

 

분류가 dp인것을 모르고 푼 문제라서

DFS로 판다가 살 수 있는 최대경로를 찾아내면 되겠다!

생각해서 구현했는데 시간초과가 나왔다.

 

그리고 나서 고민...또 고민했지만

시간을 줄일 수 있는 방법을 생각해내지 못했다.

 

답은 메모제이션을 활용하는 것이였다.

메모제이션은 DP의 핵심 기술이다.

 

메모제이션 설명 링크

https://namu.wiki/w/%EB%A9%94%EB%AA%A8%EC%9D%B4%EC%A0%9C%EC%9D%B4%EC%85%98

 

DFS에서 메모제이션을 활용한다면 실행시간을 훨씬 단축할 수 있다.

 

무튼 판다가 시작할 수 있는 위치를 전부 메모제이션을 활용한 DFS로

최대 생존 일을 구하면 된다.

 

편한 방식에 익숙해져서

기본적인 메모제이션을 생각해내지 못한 것을 반성하는 시간이 되었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q1937 {
    static int n = 0;
    static int[][] map;
    static int[][] dp;
    static int[] tx = {1, -1, 0, 0};
    static int[] ty = {0, 0, 1, -1};
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());
        map = new int[n][n];
        dp = new int[n][n];
        
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(dfs(i, j), ans);
            }
        }
        System.out.println(ans);
    }
 
    static int dfs(int i, int j) {
        if(dp[i][j] != 0) {
            return dp[i][j];
        }
        int cnt = 1;
        for (int k = 0; k < 4; k++) {
            if(i + tx[k] >= 0 && i + tx[k] < n && j + ty[k] >= 0 && j + ty[k] < n) {
                if(map[i][j] < map[i + tx[k]][j + ty[k]]) {
                    cnt = Math.max(dfs(i + tx[k], j + ty[k]) + 1, cnt);
                    dp[i][j] = cnt;
                }
            }
        }
        return cnt;
    }
}