[Java] 백준 - 1520번: 내리막 길

11월 20일(월) - 다이나믹 프로그래밍 (1520번)

1520번: 내리막 길

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

(C언어 풀이 활용)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.*;

public class Main {

    static int M,N;
    static int[][] map, dp;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        map = new int[M+1][N+1];
        dp = new int[M+1][N+1];

        for(int i=1; i<=M; i++)
        {
            st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++)
            {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[i][j] = -1;
            }
        }

        System.out.println(dfs(1,1));
    }

    static int dfs(int y, int x){
        if(y==M && x==N)
        {
            return 1;
        }

        if(dp[y][x] == -1)
        {
            dp[y][x] = 0;

            for(int i=0; i<4; i++)
            {
                int next_x = x + dx[i];
                int next_y = y + dy[i];

                if(next_x<1 || next_y<1 || next_x>N || next_y>M)
                {
                    continue;
                }
                if(map[next_y][next_x] < map[y][x])
                {
                    dp[y][x] = dp[y][x] + dfs(next_y, next_x);
                }
            }
        }

        return dp[y][x];
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ