링크 →

1520번: 내리막 길

• 아영

  • 코드
  • 시간,메모리

• 성우

  • 코드
  • 시간,메모리

• 은영

  • 코드

  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  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][N];
  		dp = new int[M][N];
  		
  		for (int i = 0; i<M; i++) {
  			Arrays.fill(dp[i], -1);
  		}
  		
  		for (int i = 0;i < M; i++) {
  			st = new StringTokenizer(br.readLine()+" ");
  			for (int j = 0; j <N; j++) {
  				map[i][j] = Integer.parseInt(st.nextToken());
  			}
  		}
  		System.out.println(dfs(0,0));
  	}
  	static int dfs(int x, int y) {
  		if(x == M-1 && y == N-1) return 1;
  		if (dp[x][y] != -1) return dp[x][y];
  		
  		int start = map[x][y];
  		dp[x][y] = 0;
  		for (int i=0; i<4; i++) {
  			int dr = x + dx[i];
  			int dc = y + dy[i];
  			
  			if (dr <0 || dr > M-1 || dc < 0 || dc > N-1) continue;
  			
  			int temp = map[dr][dc];
  			if (start > temp) {
  				dp[x][y] += dfs(dr, dc);
  			}
  		}
  		return dp[x][y];
  	}
  }
  

  • 시간,메모리

• 건

  • 코드
  • 시간,메모리

• 용문

  • 코드

  class BJ1520 {
      
      private var N: Int = 0
      private var M: Int = 0
      private var map: [[Int]] = []
      private var dp: [[Int]] = []
      
      private let dx = [0, 0, 1, -1]
      private let dy = [1, -1, 0, 0]
      
      public func solve() {
          readComponents()
          print(calc(x: 0, y: 0))
      }
      
      private func readComponents() {
          let temp = readLine()!.split(separator: " ").map { Int($0)! }
          
          N = temp[0]
          M = temp[1]
          
          map = .init(repeating: .init(repeating: 0, count: M), count: N)
          dp = .init(repeating: .init(repeating: -1, count: M), count: N)
          
          for i in 0..<N {
              map[i] = readLine()!.split(separator: " ").map { Int($0)! }
          }
      }
      
      private func calc(x: Int, y: Int) -> Int {
          if x == N - 1, y == M - 1 {
              return 1
          }
          
          if dp[x][y] == -1 {
              dp[x][y] = 0
              
              for i in 0..<4 {
                  let nx = x + dx[i]
                  let ny = y + dy[i]
                  
                  if boundCheck(x: nx, y: ny), map[nx][ny] < map[x][y] {
                      dp[x][y] += calc(x: nx, y: ny)
                  }
              }
          }
          
          return dp[x][y]
      }
      
      private func boundCheck(x: Int, y: Int) -> Bool {
          if x < 0 || x >= N || y < 0 || y >= M { return false }
          return true
      }
  }
  
  BJ1520().solve()