[백준 1520번] 내리막 길

문제 링크: 1520번 제목

https://www.acmicpc.net/problem/1520

 

P(i, j)가 (i, j)의 위치에서 출발지까지 가는 경로의 수를 나타낸다고 한다면 이는 다음과 같은 식으로 표현된다.

P(i, j) = sum({P(k, l) | (k, l)은 (i, j)와 인접 & (k, l)은 (i, j)보다 고도가 높음})

P(i, j)의 초기값을 -1로 설정해두어서 방문 여부를 표시한다면, (i, j)를 방문한 경우 P(i, j)를 바로 사용하면 되며 이는 다시 계산할 필요가 없다.

 

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

public class Main {
​​​​static int m;
​​​​static int n;
​​​​static int[][] map;
​​​​static int[][] dp;
​​​​static int[] drow = {-1, 0, 1, 0};
​​​​static int[] dcol = {0, 1, 0, -1};

​​​​public static int solution(int row, int col) {
‌​​​​// 출발지의 경로 수는 1
​​​​​​​​if (row == 1 && col == 1) return 1;
​​​​​​​​
​​​​​​​​// 이미 계산한 적이 있는 위치이면 저장해둔 값을 사용
​​​​​​​​if (dp[row][col] != -1) return dp[row][col];

​​​​​​​​int sum = 0;
​​​​​​​​for (int d = 0; d < 4; d++) {
​​​​​​​​​​​​int r = row + drow[d];
​​​​​​​​​​​​int c = col + dcol[d];

​​​​​​​​​​​​if (r<0 || c<0 || r>m || c>n) continue;
​​​​​​​​​​​​if (map[r][c] <= map[row][col]) continue;

​​​​​​​​​​​​sum += solution(r, c);
​​​​​​​​}
​​​​​​​​dp[row][col] = sum;
​​​​​​​​return sum;
​​​​}

​​​​public static void main(String[] args) throws IOException {
​​​​​​​​BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
​​​​​​​​String[] temp = bf.readLine().split(" ");
​​​​​​​​m = Integer.parseInt(temp[0]);
​​​​​​​​n = Integer.parseInt(temp[1]);

​​​​​​​​// create map
​​​​​​​​map = new int[m+1][n+1];
​​​​​​​​for (int i = 1; i <= m; i++) {
​​​​​​​​​​​​temp = bf.readLine().split(" ");
​​​​​​​​​​​​for (int j = 1; j <= n; j++)
​​​​​​​​​​​​​​​​map[i][j] = Integer.parseInt(temp[j-1]);
​​​​​​​​}

​​​​​​​​// create dp
​​​​​​​​dp = new int[m+1][n+1];
​​​​​​​​for (int i = 0; i <= m; i++)
​​​​​​​​​​​​for (int j = 0; j <= n; j++)
​​​​​​​​​​​​​​​​dp[i][j] = -1;

​​​​​​​​System.out.println(solution(m, n));
​​​​}
}