백준5569 출근 경로

작성일 | In

문제 링크

  • http://icpc.me/1256

문제 출처

  • 2010 JOI 예선 5번

사용 알고리즘

  • DP

시간복잡도

  • O(WH)

풀이

기본적인 격자 문제에 몇 가지 제약 조건이 붙은 문제입니다.
점화식의 인자를 가로, 세로 외에 추가로 2개를 더 줍시다.

  1. 첫 번째 인자가 0인 경우 동쪽으로 이동, 1인 경우 북쪽으로 이동
  2. 두 번째 인자가 0인 경우 현재 방향으로 1칸만 이동, 1인 경우 2칸 이상 이동

4가지 경우를 고려해 점화식을 세워주면 됩니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int dp[110][110][2][2]; //dir, 1 or over2

const int m = 100000;

int main(){
	int w, h; cin >> w >> h;

	for(int i=2; i<=w; i++) dp[i][1][0][0] = 1;
	for(int i=2; i<=h; i++) dp[1][i][1][0] = 1;

	for(int i=2; i<=w; i++){
		for(int j=2; j<=h; j++){
			dp[i][j][0][0] = (dp[i-1][j][0][0] + dp[i-1][j][0][1]) % m;
			dp[i][j][0][1] = dp[i-1][j][1][0];
			dp[i][j][1][0] = (dp[i][j-1][1][0] + dp[i][j-1][1][1]) % m;
			dp[i][j][1][1] = dp[i][j-1][0][0];
		}
	}

	int ans = 0;
	for(int i=0; i<2; i++) for(int j=0; j<2; j++) ans += dp[w][h][i][j];
	cout << ans%m;
}