[백준] 23083: 꿀벌 승연이 - JAVA

03 Jul 2023 in Algorithm on 다이나믹 프로그래밍

https://www.acmicpc.net/problem/23083

풀이

경로의 개수를 세야 하는 DP문제.

벌집 구조이다. 아래쪽, 오른쪽 위, 오른쪽 아래 3가지 방향으로 이동할 수 있다.

bottom-up으로 진행을 하면 오른쪽 위로 이동할 때 처리가 곤란할 것 같아서 top-down방식을 채택했다.

dp배열의 초기값을 -1로 설정하고 -1이 아닌 경우에는 dp배열의 값이 설정되었다는 것이므로 dp배열의 값을 반환했다.

구멍뚫린 칸은 0으로, (1, 1)은 1로 설정했다.

현재 칸을 (r, c)라고 할때 c가 2의 배수인 경우와 아닌 경우 탐색 해야 하는 배열이 달랐다.

if(c % 2 == 0) {
    return dp[r][c] = (doDp(r + 1, c - 1) + doDp(r, c - 1) + doDp(r - 1, c)) % MOD;
}else {
    return dp[r][c] = (doDp(r, c - 1) + doDp(r - 1, c - 1) + doDp(r - 1, c)) % MOD;
}

위와 같이 2의 배수인 경우와 아닌 경우를 나누어 탐색했다.

---

메모리: 30068KB

시간: 388ms

언어: Java 11

코드

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

public class Main {
    static int N, M;
    static long[][] dp;

    final static long MOD = 1_000_000_007;

    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());
        
        dp = new long[N + 1][M + 1];
        for(int i = 0; i < N + 1; i++) {
            for(int j = 0; j < M + 1; j++) {
                dp[i][j] = -1;
            }
        }
        dp[1][1] = 1;

        int K = Integer.parseInt(br.readLine());
        for(int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            dp[x][y] = 0;
        }

        System.out.println(doDp(N, M));

    }

    private static long doDp(int r, int c) {
        if(r < 1 || c < 1 || r > N || c > M) {
            return 0;
        }

        if(dp[r][c] != -1) {
            return dp[r][c];
        }

        if(c % 2 == 0) {
            return dp[r][c] = (doDp(r + 1, c - 1) + doDp(r, c - 1) + doDp(r - 1, c)) % MOD;
        }else {
            return dp[r][c] = (doDp(r, c - 1) + doDp(r - 1, c - 1) + doDp(r - 1, c)) % MOD;
        }
    }

}