170. 출근 경로

백준

1. Python

w, h = map(int, input().strip().split())

# 가로 x 세로 순서로 인덱스 표시할 예정
# 좌표축에서 (x, y) 읽듯이
# 3차원 행렬로 만들어줌
# arr[x][y][d] 순으로 만들기
arr =  [[[0]*4 for i in range(h+1)] for j in range(w+1)]

# 여기서 d는 총 4가지
# 0 - (x, y) 점에서 화살표가 동쪽을 향하고 있고, 회전 가능하다.
# 1 - (x, y) 점에서 화살표가 동쪽을 향하고 있고, 회전 불가능하다.
# 2 - (x, y) 점에서 화살표가 북쪽을 향하고 있고, 회전 가능하다.
# 3 - (x ,y) 점에서 화살표가 북쪽을 향하고 있고, 회전 불가능하다.

# 시작점(1,1)에서 수직, 수평으로 이동하면 해당 점에서 회전이 가능함.
# 따라서 d = 0, 2에 기록해줌
for i in range(2, w+1) :
    arr[i][1][0] = 1

for j in range(2, h+1) :
    arr[1][j][2] = 1

for i in range(2, w+1) :
    for j in range(2, h+1) :
        # (i, j) 번째에 왔을 때 동쪽을 보고 회전 가능하다면
        # (i-1, j) 번째가 동쪽을 보고 회전이 가능하거나, (i-1, j)번째가 동쪽을 보고 회전이 불가능한 상태
        arr[i][j][0] = arr[i-1][j][0] + arr[i-1][j][1]

        # (i, j) 번째에 왔을 때 동쪽을 보고 회전 불가능하다면
        # (i-1, j) 번째가 북쪽을 보고 회전이 가능한 경우
        arr[i][j][1] = arr[i-1][j][2]

        # (i, j) 번째에 왔을 때 북쪽을 보고 회전 가능하다면
        # (i, j-1) 번째가 북쪽을 보고 회전이 가능하거나, (i, j-1)번째가 북쪽을 보고 회전이 불가능한 상태
        arr[i][j][2] = arr[i][j-1][2] + arr[i][j-1][3]

        # (i, j) 번째에 왔을 때 북쪽을 보고 회전 불가능하다면
        # (i, j-1) 번째가 동쪽을 보고 회전이 가능한 경우
        arr[i][j][3] = arr[i][j-1][0]

# w,h 번째에 도착했을 때 총 경우의 수를 다 더해줌.(방향과 회전 가능여부 고려)
print(sum(arr[w][h]) % 100000)

2. C++

참고

#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;
}