[BOJ 5569 // C++] 출근 경로

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 5569번 문제인 출근 경로이다.

문제는 아래 링크를 확인하자.

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

5569번: 출근 경로

각 교차로에 도달하는 경로를 다음과 같이 넷으로 분류하자.

 

 

0. 직전 교차로에서 동쪽으로 이동, 이번에 동쪽과 북쪽 이동 가능

1. 직전 교차로에서 북쪽으로 이동, 이번에 동쪽과 북쪽 이동 가능

2. 직전 교차로에서 동쪽으로 이동, 이번에 동쪽으로만 이동 가능

3. 직전 교차로에서 북쪽으로 이동, 이번에 북쪽으로만 이동 가능

(4. 아직 이동 안함 = 출발점)

 

위 상태들을 이용하여 dp 식을 적절히 세운 후 문제를 해결하자.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[101][101][5]; // 0:이전움직임R 1:이전움직임C 2:이전움직임R, 막꺾음 3:이전움직임C, 막꺾음, 4: 이전기록없음(1,1)


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

	int R, C; cin >> R >> C;
	arr[1][1][4] = 1;
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			if (r == 1 && c == 1) continue;
			arr[r][c][0] = (arr[r - 1][c][0] + arr[r - 1][c][2] + arr[r - 1][c][4]) % 100000;
			arr[r][c][1] = (arr[r][c - 1][1] + arr[r][c - 1][3] + arr[r][c - 1][4]) % 100000;
			arr[r][c][2] = arr[r - 1][c][1];
			arr[r][c][3] = arr[r][c - 1][0];
		}
	}

	int ans = 0;
	for (int i = 0; i < 5; i++) ans += arr[R][C][i];
	cout << ans % 100000;
}