[Python] BOJ 17069 - 파이프 옮기기 2

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

17069번: 파이프 옮기기 2

# 각 좌표마다 경우의 수가 3가지이므로(가로, 세로, 대각선) 3차원 배열을 사용하였다.

 

# 처음 파이프는 (0, 0), (0, 1)에 가로로 놓여있으므로 dp[0][1][0]에 1을 넣어준다.

   -> (0, 1)에 파이프 끝이 있고, 가로로 놓여있다는 뜻이다.

       (dp[x][y][0] = (x, y)에 파이프 끝이 있고, 가로로 놓여있다는 뜻

        dp[x][y][1] = (x, y)에 파이프 끝이 있고, 세로로 놓여있다는 뜻

        dp[x][y][2] = (x, y)에 파이프 끝이 있고, 대각선으로 놓여있다는 뜻)

 

# 맨 윗 줄은 벽이 만나기 전까지 계속 가로로만 놓을 수 있으므로 m[0][i]가 1이 되기 전까지

   dp[0][i][0]에 1을 넣어준다.

 

# 직접 dp테이블을 그려보면 (1, 1)부터 (N-1, 1)까지는 파이프를 놓을 수 없으므로 0을 그대로 나두고

   (1, 2)부터 dp테이블을 갱신해준다.

 

# 현재 파이프 끝을 놓으려는 좌표가 비어있어야 파이프를 놓을 수 있으므로 m[i][j]가 0이면 

   dp[i][j][0], dp[i][j][1]을 구해주고 대각선은 현재 놓으려는 좌표뿐만 아니라 위, 왼쪽도 비어있어야

   놓을 수 있으므로 m[i][j-1]과 m[i-1][j]까지 추가로 확인해준다.

 

# dp[i][j][0] 같은 경우, 가로로 놓을 수 있는 경우는

   (가로로 놓은 파이프 오른쪽에 이어서 놓는 경우와 대각선으로 놓은 파이프 오른쪽에 이어서 놓는 경우)

   2가지이므로 dp[i][j-1][0] + dp[i][j-1][2] 라고 표현할 수 있다.

   이와 마찬가지로 dp[i][j][1], dp[i][j][2]도 갱신해준다.

 

# dp테이블을 모두 갱신해 준 뒤, dp[-1][-1]에는 (N, N)에 파이프를 놓는 경우의 수가 3가지 구해져 있다.

   그 3가지 경우를 합해서 출력해주면 끝

 

import sys
input = sys.stdin.readline
N = int(input())
m = [list(map(int,input().split())) for _ in range(N)]
dp = [[[0] * 3 for _ in range(N)] for _ in range(N)]
# dp[x][x][0] = 가로, dp[x][x][1] = 세로, dp[x][x][2] = 대각선
dp[0][1][0] = 1
for i in range(1, N):
	if m[0][i] == 1:
		break
	else:
		dp[0][i][0] = 1

for i in range(1, N):
	for j in range(2, N):
		if not m[i][j]:
        	# 가로
			dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][2]
		if not m[i][j]:
        	# 세로
			dp[i][j][1] = dp[i-1][j][1] + dp[i-1][j][2]
		if not m[i][j-1] and not m[i-1][j] and not m[i][j]:
        	# 대각선
			dp[i][j][2] = dp[i-1][j-1][1] + dp[i-1][j-1][0] + dp[i-1][j-1][2]

print(sum(dp[-1][-1]))

(solved.ac 티어: 골드 5)