[14553번] The Way

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

2. 점화식 세우는 방법

바로 그림을 통해 DP를 생각해보자.

DP[i][j]의 정의는 i에서 j로 갈때 DP값을 의미한다.

i-1번째에서 i번째로 오기위한 3가지 DP를 우선 확인하고자 한다.

이때의 DP는 DP[i][2] = DP[i - 1][1] + DP[i - 1][2] + DP[i - 1][3] 임을 알 수 있다.

그다음 DP를 보면

이때의 DP는 DP[i][3] = DP[i - 1][1] + DP[i - 1][2] + DP[i - 1][3] 임을 알 수 있다.

마지막 DP또한 

DP[i][1] = DP[i - 1][1] + DP[i - 1][2] + DP[i - 1][3] 임을 알 수 있다.

결국

DP[i][1] = DP[i][2] = DP[i][3] = DP[i - 1][1] + DP[i - 1][2] + DP[i - 1][3] 임을 알 수 있다.

이제 왼쪽으로도 움직 일 수 있는 경우까지 포함해보자.

어떤점 i,j에서 왼쪽으로 움직였다가 도착점으로 가기 위한 행동은 아래그림에서는 i-3번째에서 시작하여 왼쪽으로 움직일 수 있게된다.

결국 1번째, 2번째, ... , i-2번째까지 된다.(i-1번째에선 왼쪽 화살표가 생길 수 없게된다.)

고로 이 과정을 모두 추가해주면 다음과 같다.

for(int j=1;j<i-1;j++)

{

     d[i][1] += d[j][3];

     d[i][3] += d[j][1];

}

이제 마지막으로 아래 그림과 같은 경우를 고려해주게 된다면 결국 +1을 통해 문제를 해결할 수 있게된다.

소스 코드 : 

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 26 27 28 29 30 31

#include <cstdio> int mod = 1000000009; long long d[1001][4]; int main(){          int n;          scanf("%d",&n);          d[1][1] = d[1][2] = d[1][3] = 1;          for(int i=2;i<=n;i++){              d[i][1] = d[i][2] = d[i][3] = d[i-1][1] + d[i-1][2] + d[i-1][3];                 for(int j=1;j<i-1;j++){             d[i][1] += d[j][3];             d[i][3] += d[j][1];         }                  d[i][1] %= mod;         d[i][2] %= mod;         d[i][3] = (d[i][3] + 1) % mod;     }               printf("%lld\n",d[n][3]);     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus