[백준 14430] 자원 캐기

 

처음에는 DFS + 완전탐색으로 풀었는데 당연히 시간초과가 났다.

 

틀린소스 (타임아웃)

public class Main {
    
    static int n;
    static int m;
    static int a[][];
    static int dx[] = {0, 1};
    static int dy[] = {1, 0};
    static int max = 0;
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        a = 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++)
                a[i][j] = Integer.parseInt(st.nextToken());
        }
        
        dfs(1, 1, 0);
        System.out.println(max);
    }
    
    public static void dfs(int x, int y, int cnt) {
        if(x == n && y == m) {
            max = Math.max(max, cnt);
            return;
        }
        
        for(int i=0; i<2; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(1 <= nx && nx <= n && 1 <= ny && ny <= m) {
                if(a[nx][ny] == 1) dfs(nx, ny, cnt+1);
                else dfs(nx, ny, cnt);
            }
        }
    }
}

 

 

아무래도 DP문제인것 같아 방식을 바꿨다.

 

(1, 1)에서 (N, M)까지 광석을 최대한으로 캐며 진행하는 방법은 그리디하게만 진행되어 때려치웠고,

(N, M)에서 (1, 1)까지 역주행하며 광석의 양을 구했다.

 

탑다운 방식으로 재귀하며 왼쪽, 위 로 이동하며 최대값을 반환하게 했다.

 

public class Main {
    
    static int n;
    static int m;
    static int a[][];
    static int dp[][];
    
    public static int f(int x, int y) {
        if(x < 1 || y < 1) return 0;
        if(dp[x][y] != -1) return dp[x][y];
        
        dp[x][y] = a[x][y];
        dp[x][y] += Math.max(f(x-1, y), f(x, y-1));
        return dp[x][y];
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        
        a = new int[n+1][m+1];
        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++)
                a[i][j] = Integer.parseInt(st.nextToken());
        }
        
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
                dp[i][j] = -1;
        
        System.out.println(f(n, m));
    }
}