1520번: 내리막 길
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다.
www.acmicpc.net
boj 1937 욕심쟁이 판다
www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중
emoney96.tistory.com
이 문제와 비슷한 풀이입니다.
dfs + dp를 사용하며
위의 문제는 칸의 수를 세어주었지만 이 문제는 (0, 0)에서 (N - 1, M - 1)까지 도달할 수 있는 경우의 수를 세어주는 문제입니다.
현재 칸보다 높이가 더 낮은 지점으로만 이동합니다.
(N - 1, M - 1)에 도달하면 1을 리턴하고 이미 방문한 좌표에는 해당 좌표의 dp[x][y]를 리턴해줍니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][] = new int[500][500];
static int dp[][] = new int[500][500];
static int direct[][] = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
static int N, M;
static int func(int x, int y) {
if (x == N - 1 && y == M - 1)
return 1;
if (dp[x][y] != -1)
return dp[x][y];
dp[x][y] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + direct[i][0];
int ny = y + direct[i][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M)
continue;
if (list[x][y] <= list[nx][ny])
continue;
dp[x][y] += func(nx, ny);
}
return dp[x][y];
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1);
st = new StringTokenizer(br.readLine());
for (int j = 0; j < M; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
System.out.println(func(0, 0));
}
}
|
cs |
'algorithm > dp' 카테고리의 다른 글
| boj 10800 컬러볼 (0) | 2021.04.09 |
|---|---|
| boj 12869 뮤탈리스크 (0) | 2021.04.04 |
| boj 1937 욕심쟁이 판다 (0) | 2021.03.28 |
| boj 2201 이친수 찾기 (2) | 2021.03.24 |
| boj 2228 구간 나누기 (0) | 2021.03.21 |