[백준]5569 출근경로 #dp

1. 상하 뒤집기

문제를문제에서는 왼쪽아래부터 오른쪽위 지점까지 이동하는것으로 되어 있으나, 어차피 경우의 수만 구하면되고, 대칭이므로 리스트의 형태에 맞게 왼쪽위(0,0)에서 오른쪽아래(R,C)로 가는것으로 생각한다.

​

2. 가능한 경우를 삼차원에 저장

연속으로 꺾는것은 안된다. 이는 (이전)과 (이전전)의 이동에 따라 현재의 이동이 제한된다는 것을 말한다.

이를 고려해주기 위해 (i,j)위치에 이전 이동과 이전전 이동을 저장해야한다. 이를 위해 삼차원 배열을 활용한다.

다행히 이동은 최단거리로만 하기 때문에 오른쪽 or 아래로만 이동한다. 즉 가능한 경우의 수는

1) 아래 오른쪽

2) 오른쪽 오른쪽

3) 오른쪽 아래

4) 아래 아래

총 4가지로 볼 수 있다. 만약 상하좌우 모두 움직일 수 있다면 16가지가 나왔을 것이다.

그리고 위의 네가지 경우를 삼차원 벡터에 저장한다.

1) 아래 아래 - dp[i][j][0]

2) 오른쪽 아래 - dp[i][j][1]

3) 오른쪽 오른쪽 - dp[i][j][2]

4) 아래 오른쪽 - dp[i][j][3]

​

3. 점화식의 구성.

위에서 내려오는 점과 왼쪽에서 오른쪽으로 오는 점을 생각해준다.

​

1) 위에서 내려오는 점 (dp[i-1][j])

dp[i-1][j][0](아래,아래) or dp[i-1][j][1](오른쪽, 아래) or dp[i-1][j][2](오른쪽, 오른쪽) 가 있다.

이때 dp[i-1][j][0]과 dp[i-1][j][1]은 내려오면 모두 (아래,아래)가 되고

dp[i-1][j][2]가 내려오면 (오른쪽,아래)가 된다. 이를 표로 나타내면

 

2) 왼쪽에서 오는점 (dp[i][j-1] )

 

4. 1행은 모두 (오른쪽,오른쪽)으로 채우고, 1열은 모두 (아래,아래)로 채운다.

​

5. 탐색 순서.

이동은 항상 최단거리로 하기 때문에 오른쪽 or 아래로만 한다. 이는 (i,j)까지의 이동경로 경우의 수를 구하기 위해선 (i,j-1)과 (i-1,j)의 합만을 고려해 주면 된다는 뜻이 된다.(위나 왼쪽으로 거슬러 가는 경우는 없으니까)

따라서 탐색은

for (int i=0; i<=N; i++) {
  for (int j=0; j<=C; j++ {
     탐색
  }
}

 

6. 소스코드

#include <iostream>
#include <algorithm>

using namespace std;
long long dp[101][101][4];

int main() {
	int R, C;
	cin >> C >> R;
	int mod = 100000;
	for (int i = 1; i <= R; i++) {
		dp[i][1][0] = 1;
	}
	for (int j = 1; j <= C; j++) {
		dp[1][j][2] = 1;
	}

	for (int i = 2; i <= R; i++) {
		for (int j = 2; j <= C; j++) {
			// 위에서 내려오는것
			dp[i][j][0] = (dp[i - 1][j][1] + dp[i - 1][j][0]) % mod;
			dp[i][j][1] = dp[i - 1][j][2];

			// 왼쪽에서 오는것
			dp[i][j][2] = (dp[i][j - 1][3] + dp[i][j - 1][2]) % mod;
			dp[i][j][3] = dp[i][j - 1][0];
		}
	}
	int ans = 0;
	for (int k = 0; k < 4; k++) {
		ans += dp[R][C][k];
	}
	cout << ans % mod;

	return 0;
}