Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

23. 동적 계획법2

조금 더 어려운 동적 계획법 문제를 풀어 봅시다.

Java / Python

3. 내리막 길

1520번

내리막길로만 이동하는 경우의 수를 구하는 문제

이번 문제는 지도가 주어질 때 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하는 문제입니다.

• Java

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

public class Main {
	static int M;
	static int N;
	static int[][] map;
	static int[][] dp;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		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++) {
			st = new StringTokenizer(br.readLine());   
			for(int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
				dp[i][j] = -1;
            }   
		}
		bw.write(solve(0,0) + "\n");  
        
		bw.flush();
		bw.close();
		br.close();
	}
	public static int solve(int x, int y) {
		if(x == M - 1 && y == N - 1) return 1;
        
		if(dp[x][y] == -1) { // 경로의 수가 계산된 적 없고, 방문한 적 없는 경우만 계산
			dp[x][y] = 0;
            
			// 위로 이동
			if(x > 0 && map[x][y] > map[x-1][y]) {
				dp[x][y] += solve(x-1, y);
			}
			// 아래로 이동
			if(x < M - 1 && map[x][y] > map[x+1][y]) {
				dp[x][y] += solve(x+1, y);
			}
			// 왼쪽으로 이동
			if(y > 0 && map[x][y] > map[x][y-1]) {
				dp[x][y] += solve(x, y-1);
			}
			// 오른쪽으로 이동
			if(y < N - 1 && map[x][y] > map[x][y+1]) {
				dp[x][y] += solve(x, y+1);
			}
		}
		return dp[x][y];
	}
}

• Python

import sys
sys.setrecursionlimit(10000) # RecursionError 방지
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

m, n = map(int, sys.stdin.readline().split())
a = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
c = [[-1]*n for _ in range(m)]

def dfs(x, y):
    if x == m - 1 and y == n - 1:
        return 1
    if c[x][y] != -1:
        return c[x][y]
    c[x][y] = 0
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < m and 0 <= ny < n:
            if a[nx][ny] < a[x][y]:
                c[x][y] += dfs(nx, ny)
    return c[x][y]

print(dfs(0, 0))