문제풀이/백준
[백준] 22236: 🛫🛬가희와 비행기 - JAVA
빈둥벤둥
2021. 8. 18. 16:10
[백준] 22236: 가희와 비행기
22236번: 가희와 비행기
가희는 김포 공항에서 김해 공항까지 비행기를 타고 가려고 합니다. 비행기가 수평 방향으로 1만큼 이동하였을 때, 비행기의 고도는 1만큼 변화합니다. (상승 또는 하강) 비행기가 상승하거나
www.acmicpc.net
풀이
🪑 DP유형 스러운 DP문제로 어렵지 않은 점화식으로 풀 수 있는 문제였다!
📝 문제를 정리해 보자!
- 수평 방향으로의 이동 변화량과 고도 변화량은 동일하다.
- 비행기는 착륙까지 비행 방향을 바꾸지 않는다. 즉, 고도만 바뀐다.
- 수평 방향으로 D만큼 이동했을 때 착륙 지점의 고도는 항상 0이다. 또한 착륙 이전에는 고도가 0이면 안된다.
- 위의 조건을 모두 만족하여 착륙지점에 착륙하는 경우의 수를 모두 구한다.
🙋♀️ 일단 점화식을 구해보자!
- 현재 이동 거리가 i이고, 현재 고도가 j라고 했을때 현재 까지 이동할 수 있는 경우의 수를 구하는 식은 아래와 같다.
- dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1]
- 현재 위치에서의 이동 경우의 수는 이전 위치에서 고도가 하나 낮을때의 경우의수 + 고도가 하나 높을 때의 경우의 수이다.
- 이동 거리 변화량과 고도 변화량은 동일하므로 1칸 이동시 1칸만큼 낮아지거나, 높아질 수 밖에 없기 때문이다!
🔧 문제를 따라가며 풀어보자!
- 점화식을 사용하여 bottom-up 방식으로 순회해 주었다.
- 도착지 이전 까지의 경우의 수만 구하고, 도착 했을 때는 무조건 고도가 0이므로 이전 위치에서 고도가 1일때의 경우의 수가 정답이 된다.
🔹 도착 했을 때는 무조건 고도가 0이므로 이전 위치에서 고도가 1일때의 경우의 수가 정답이 된다.
- 식으로 표현하면 다음과 같다.
- dp[d - 1][1] % m
코드
|
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
|
//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);
}
}
|
cs |