[백준] 1520 내리막길

문제보기

그냥 도착지점에서 올라가는걸로 구했다. 요새 계속 탑다운 방식만 썼더니 이쪽으로 기울어짐..

import java.util.*;
import java.io.*;

public class Main{
  static int n;
  static int m;
  static int[][] map;
  static int[][] d;
  static int[] dx = {1, -1, 0, 0};
  static int[] dy = {0, 0, 1, -1};

  static int go(int x, int y){
    if( x == 0 && y == 0 ){ // 출발지에 도착하면 탈출쓰
      return 1;
    }
    if(d[x][y] != -1){ // 메모된거 꺼내쓰기
      return d[x][y];
    }

    int ans = 0; // 답을 담을 변수
    for(int k = 0 ; k < 4 ; k++){ // 다음 좌표 소환
      int nx = x + dx[k];
      int ny = y + dy[k];

      if( nx >= 0 && nx < n && ny >= 0 && ny < m){ // 지도상에 있다면
        if(map[nx][ny] > map[x][y]){ // 그리고 오르막길이라면
          ans += go(nx, ny); // 간닷~
        }
      }

    }

    d[x][y] = ans; // 메모이제이션
    return ans; // 날 부른 go에게 보낼 값
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    n = Integer.parseInt(st.nextToken());
    m =  Integer.parseInt(st.nextToken());
    map = new int[n][m];
    d = new int[n][m];
    for(int i = 0 ; i < n ; i++){
      st = new StringTokenizer(br.readLine());
      for(int j = 0 ; j < m ; j++){
        map[i][j] = Integer.parseInt(st.nextToken());
        d[i][j] = -1;
      }
    }
    System.out.println(go(n-1, m-1));
  }
}