[백준 14585] 사수빈탕

 

완전탐색으로 풀기엔 주어진 시간이 너무 짧다.

 

사탕배열을 만들어 사탕이 있는지 여부를 저장해놓고

DP배열로 매 탐색마다 최대로 먹을수 있는 사탕의 개수를 갱신한다.

 

public class Main {
    
    static boolean a[][];
    static int dp[][];
    
    public static int findCandy(int x, int y, int m) {
        if(x == 301 || y == 301) return 0;
        if(m == 0) return 0;
        if(dp[x][y] != -1) return dp[x][y];
        
        if(a[x][y]) dp[x][y] = m;
        else dp[x][y] = 0;
        dp[x][y] += Math.max(findCandy(x+1, y, m-1), findCandy(x, y+1, m-1));
        return dp[x][y];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        a = new boolean[301][301];
        dp = new int[301][301];
        for(int i=0; i<301; i++)
            for(int j=0; j<301; j++)
                dp[i][j] = -1;
        
        for(int i=0; i<n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            a[x][y] = true;
        }
        
        System.out.println(findCandy(0, 0, m));
    }
}