반응형
17070번: 파이프 옮기기 1 (acmicpc.net)
풀이
- 파이프를 움직여 해당 구간까지 옮길 수 있는 방법의 개수를 구하는 문제이다.
- 현재 파이프의 상태가 가로인지 , 세로인지 , 대각선인지에 따라서 움직일 수 있는 경우가 다르므로 3차원 dp 배열을 통해 각 경우를 구분하고 구분된 경우에 따라서 다음 움직임을 구하도록 하였다.
- dp[k][i][t] 에서 i와 t는 본래 2차원 dp 배열의 인덱스 , k는 0 일 때 가로 , 1 일 때 세로 , 2일 때 대각선
- 현재 가로의 경우 -> 움직일 곳에 벽이 있는지 체크 후 없다면 대각선 / 가로 방향 dp 배열 업데이트
- 현재 세로의 경우 -> 움직일 곳에 벽이 있는지 체크 후 없다면 대각선 / 세로 방향 dp 배열 업데이트
- 현재 대각선의 경우 -> 움직일 곳에 벽이 있는지 체크 후 없다면 대각선 / 가로 / 세로 방향 dp 배열 업데이트
import sys
n = int(sys.stdin.readline())
stack = []
for _ in range(n):
stack.append(list(map(int, sys.stdin.readline().split(" "))) + [1])
sub = [1]*(n+1)
stack.append(sub)
dp = [[[0 for _ in range(n+1)] for _ in range(n+1)] for _ in range(3)] #가로 세로 대각
dp[0][0][1] = 1
for i in range(0,n):
for t in range(0,n):
for k in range(0,3):
if dp[k][i][t] > 0:
if k == 0:
if stack[i][t+1] != 1:
dp[0][i][t+1] += dp[0][i][t]
if stack[i+1][t+1] != 1 and stack[i+1][t] != 1 and stack[i][t+1] != 1:
dp[2][i+1][t+1] += dp[0][i][t]
elif k == 1:
if stack[i+1][t] != 1:
dp[1][i+1][t] += dp[1][i][t]
if stack[i+1][t+1] != 1 and stack[i+1][t] != 1 and stack[i][t+1] != 1:
dp[2][i+1][t+1] += dp[1][i][t]
elif k == 2:
if stack[i][t + 1] != 1:
dp[0][i][t+1] += dp[2][i][t]
if stack[i + 1][t + 1] != 1 and stack[i+1][t] != 1 and stack[i][t+1] != 1:
dp[2][i+1][t+1] += dp[2][i][t]
if stack[i + 1][t] != 1:
dp[1][i+1][t] += dp[2][i][t]
if stack[n-1][n-1] == 1:
print(0)
else:
print(dp[0][n-1][n-1] + dp[2][n-1][n-1] + dp[1][n-1][n-1])
반응형
'코딩 > 백준' 카테고리의 다른 글
알고리즘 - Python / 백준 - 1068번 : 트리 (0) | 2021.10.07 |
---|---|
알고리즘 - Python / 백준 - 1991번 : 트리 순회 (0) | 2021.09.26 |
알고리즘 - Python / 백준 - 1789번 : 수들의 합 (0) | 2021.09.25 |
알고리즘 - Python / 백준 - 11725번 : 트리의 부모 찾기 (0) | 2021.09.25 |
알고리즘 - Python / 백준 - 1932번 : 정수 삼각형 (0) | 2021.09.21 |