반응형

문제 : http://boj.kr/22236
티어 : 골드4
이 문제는 다이나믹 프로그래밍(DP, Dynamic Programming)을 이용하여 접근 할 수 있는 문제이다.
비행기가 $x$축의 양의 방향으로 $+1$이동할 때, 비행기의 고도는 $\pm1$만큼 변화한다.
이때, 비행기의 고도가 출발, 도착시를 제외하고 $0$(여기서는 1)이 되면 안되므로 이를 조건문으로 처리해주면 된다.
$i$ : 0으로부터 $x$축의 양의 방향으로 이동한 거리
$j$ : 비행기의 현재 고도 (여기서는 1부터 시작한다.)
$N$ : 문제에서 주어진 $d$
$M$ : 문제에서 주어진 $m$
라고 정의하자.
"비행기가 $x$축의 양의 방향으로 $+1$이동할 때, 비행기의 고도는 $\pm1$만큼 변화한다."를 이용하면,
DP[i][j] = DP[i-1][j-1]%M+DP[i-1][j+1]%M (단, DP[i-1][j-1] $>0$ 이거나, DP[i-1][j+1] $>0$)
이라는 관계식을 얻어 낼 수 있다.
이때, 비행기가 착륙하기 위해서는 $N-1$지점에서 비행기의 고도는 $2$이여야 한다.
따라서 출력할 때, DP[N-1][2]%M을 출력해 주어야 한다.
int N, M;
cin >> N >> M;
dp[0][1]=1;
dp[1][2]=1;
for(int i=2; i<N; i++) {
for(int j=1; j<4001; j++) {
if(dp[i-1][j-1]>0 || dp[i-1][j+1]>0) {
switch(j) {
case 1:
dp[i][j]=0;
break;
default:
dp[i][j]=(dp[i-1][j-1]%M+dp[i-1][j+1]%M);
break;
}
}
}
}
cout << (dp[N-1][2]%M);
반응형
'BOJ' 카테고리의 다른 글
| [C++] 23827 - 수열(Easy) (0) | 2021.12.17 |
|---|---|
| [C++] BOJ 11726 - 2xn 타일링 (0) | 2021.09.05 |
| [C++] BOJ 18108 - 1998년생인 내가 태국에서는 2541년생?! (0) | 2021.09.04 |
| [C++] BOJ 11659 - 구간 합 구하기 4 (0) | 2021.09.04 |
| [C++] BOJ 2747 - 피보나치 수 (0) | 2021.09.04 |