[Python/파이썬] 백준 5569번 출근 경로

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

 

코드

w, h = map(int, input().split())
dp = [[[0]*4 for _ in range(h)] for _ in range(w)]

# 값 초기화
for i in range(1, w):
    dp[i][0][1] = 1
for j in range(1, h):
    dp[0][j][3] = 1

for i in range(1, w):
    for j in range(1, h):
        dp[i][j][0] = dp[i-1][j][3]  # 계속 오른쪽으로 가다가 이번에 위로 온 경우
        dp[i][j][1] = (dp[i-1][j][0]+dp[i-1][j][1]) % 100000    # 계속 위로
        dp[i][j][2] = dp[i][j-1][1]  # 계속 위로 가다가 이번에 오른쪽으로 온 경우
        dp[i][j][3] = (dp[i][j-1][2]+dp[i][j-1][3]) % 100000    # 계속 오른쪽으로

print(sum(dp[w-1][h-1]) % 100000)

 

어렸을 때는 이런 식으로 길의 경로의 개수를 구했던 기억이 있다.

여기서 아이디어를 얻어서 DP 알고리즘으로 풀이하게 되었다. 다만 다른점은 " 교차로에서 방향을 바꾼 후, 1 블록만 이동한 후 다시 방향을 바꿀 수 없다"라는 문제의 조건을 고려하기 위해 각 칸에 도달하는 경우의 수를 4가지 경우로 나누어서 저장했다는 점이다. 그렇기에 각 칸까지 가는 경우의 수를 저장하는 리스트 dp에서 dp[i][j]는 4개의 원소로 구성된다.

 

1. 계속 오른쪽으로 가다가 이번에 위로 이동한 경우

2. 이전에도 위로 이동했고, 이번에도 위로 이동하는 경우

3. 계속 위로 가다가 이번에 오른쪽으로 이동한 경우

4. 이전에도 오른쪽으로 이동했고, 이번에도 오른쪽으로 이동하는 경우

 

이 4가지 경우의 수를 dp[i][j][0]부터 dp[i][j][3]까지 각각 저장한다. 그리고 각 칸의 값들은 다음과 같은 과정을 통해 채워나간다.

for i in range(1, w):
    for j in range(1, h):
        dp[i][j][0] = dp[i-1][j][3]  # 계속 오른쪽으로 가다가 이번에 위로 온 경우
        dp[i][j][1] = (dp[i-1][j][0]+dp[i-1][j][1]) % 100000    # 계속 위로
        dp[i][j][2] = dp[i][j-1][1]  # 계속 위로 가다가 이번에 오른쪽으로 온 경우
        dp[i][j][3] = (dp[i][j-1][2]+dp[i][j-1][3]) % 100000    # 계속 오른쪽으로