algorithm/dp
boj 5569 출근 경로
와이에쓰
2021. 2. 6. 15:38
5569번: 출근 경로
상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대
www.acmicpc.net
저는 4차원배열로 dp를 구성하였습니다.
dp[x][y][t][chk]
x, y 좌표
t : 현재 진행방향 (0 -> x / 1 -> y)
chk : 방향 변경 가능 여부 (0 -> 변경 불가능 / 1 -> 변경 가능)
현재 진행 방향에서 chk = 0이면 현재 진행방향으로 이동해야합니다.
chk = 1이면 현재 진행방향, 다른 방향 모두 탐색합니다.
모든 경우의 수를 계산하여 100000으로 나눈 나머지를 출력합니다.
|
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
54
55
56
57
58
|
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 final int MOD = 100000;
static int dp[][][][];
static int N, M;
static int func(int x, int y, int t, int chk) {
if (x <= 0 || y <= 0 || x > N || y > M)
return 0;
if (x == N && y == M)
return dp[x][y][t][chk] = 1;
if (dp[x][y][t][chk] != -1)
return dp[x][y][t][chk];
dp[x][y][t][chk] = 0;
if (t == 1) {
if (chk == 1) {
dp[x][y][t][chk] = (dp[x][y][t][chk] + func(x, y + 1, t, chk) + func(x + 1, y, 1 - t, 1 - chk)) % MOD;
} else {
dp[x][y][t][chk] = (dp[x][y][t][chk] + func(x, y + 1, t, 1 - chk)) % MOD;
}
} else {
if (chk == 1) {
dp[x][y][t][chk] = (dp[x][y][t][chk] + func(x + 1, y, t, chk) + func(x, y + 1, 1 - t, 1 - chk)) % MOD;
} else {
dp[x][y][t][chk] = (dp[x][y][t][chk] + func(x + 1, y, t, 1 - chk)) % MOD;
}
}
return dp[x][y][t][chk];
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
dp = new int[N + 1][M + 1][2][2];
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
Arrays.fill(dp[i][j][0], -1);
Arrays.fill(dp[i][j][1], -1);
}
}
}
public static void main(String[] args) throws Exception {
input();
System.out.println((func(1, 1, 0, 0) + func(1, 1, 1, 0)) % MOD);
}
}
|
cs |