Baekjoon 5569 출근경로

Link https://www.acmicpc.net/problem/5569

소스결과 2144 KB / 0 ms

언어 C++ 17

출처 Baekjoon, JOI

분류 다이나믹 프로그래밍

 

설명

1,1 에서 n,m까지 가는 조건에 맞는 모든 경로를 탐색하여라

 

해당 소스코드는 JusticeHui님의 https://justicehui.github.io/joi/2019/02/10/BOJ5569/ 를 참고하였습니다.

 

DP는 아무리해도 어렵다.

조건만 없었으면 이해하겠지만 DP에 방향이나 조건을 추가해주는 방법은 아직 어렵다.

 

알고리즘

DP에는 취약하여 링크를 참고하여주시기바랍니다.

 

소스코드

 

#include <iostream>

using namespace std;

const short MAX = 100;
const int MOD = 100000;

int dp[MAX][MAX][2][2];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int h, w; cin >> w >> h;

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

	for (int i = 1; i < w; i++) {
		for (int j = 1; j < h; j++) {
			dp[i][j][0][0] = (dp[i - 1][j][0][0] + dp[i - 1][j][0][1]) % MOD;
			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]) % MOD;
			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 - 1][h - 1][i][j];

	cout << ans % MOD;

	return 0;
}