[백준] 22236: 🛫🛬가희와 비행기 - JAVA

[백준] 22236: 가희와 비행기

22236번: 가희와 비행기

풀이

🪑 DP유형 스러운 DP문제로 어렵지 않은 점화식으로 풀 수 있는 문제였다!

 

📝 문제를 정리해 보자!

• 수평 방향으로의 이동 변화량과 고도 변화량은 동일하다.
• 비행기는 착륙까지 비행 방향을 바꾸지 않는다. 즉, 고도만 바뀐다.
• 수평 방향으로 D만큼 이동했을 때 착륙 지점의 고도는 항상 0이다. 또한 착륙 이전에는 고도가 0이면 안된다.
• 위의 조건을 모두 만족하여 착륙지점에 착륙하는 경우의 수를 모두 구한다.

 

🙋‍♀️ 일단 점화식을 구해보자!

• 현재 이동 거리가 i이고, 현재 고도가 j라고 했을때 현재 까지 이동할 수 있는 경우의 수를 구하는 식은 아래와 같다.
• dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1] 
• 현재 위치에서의 이동 경우의 수는 이전 위치에서 고도가 하나 낮을때의 경우의수 + 고도가 하나 높을 때의 경우의 수이다.
• 이동 거리 변화량과 고도 변화량은 동일하므로 1칸 이동시 1칸만큼 낮아지거나, 높아질 수 밖에 없기 때문이다!

 

 

🔧 문제를 따라가며 풀어보자!

1. 점화식을 사용하여 bottom-up 방식으로 순회해 주었다.
2. 도착지 이전 까지의 경우의 수만 구하고, 도착 했을 때는 무조건 고도가 0이므로 이전 위치에서 고도가 1일때의 경우의 수가 정답이 된다.

 

🔹 도착 했을 때는 무조건 고도가 0이므로 이전 위치에서 고도가 1일때의 경우의 수가 정답이 된다.

- 식으로 표현하면 다음과 같다.

- dp[d - 1][1] % m

 

 

코드

//22236: 가희와 비행기
import java.io.*;
import java.util.*;
 
public class Main {
    public static void main(String[] args) throws IOException {
        //입력
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String str = bf.readLine();
        StringTokenizer st = new StringTokenizer(str);
        int d = Integer.parseInt(st.nextToken());
        long m = Long.parseLong(st.nextToken());
        //입력 끝
 
        long[][] dp = new long[4001][4001];
        dp[1][1] = 1;
        for(int i = 2; i < d; i++) {
            for(int j = 0; j <= i; j++) {
                if(j == 0) continue;
                else dp[i][j] += (dp[i - 1][j - 1] + dp[i - 1][j + 1] % m);
            }
        }
        System.out.println(dp[d - 1][1] % m);
    }
}