[C++] BOJ 22236 - 가희와 비행기

문제 : 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);