[백준 17096번] 파이프 옮기기 2

박형진·2022년 7월 13일
0

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


1. 코드

'''
		=input=
        4
        0 0 0 0
        0 0 0 0
        0 0 0 0
        0 0 0 0
        
        =dp print=
        [[0, 0, 0], [1, 0, 0], [1, 0, 0], [1, 0, 0]]
        [[0, 0, 0], [0, 0, 0], [0, 0, 1], [1, 0, 1]]
        [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 1, 1]]
        [[0, 0, 0], [0, 0, 0], [0, 1, 0], [0, 2, 1]]
        
        =output=
        3
'''

import sys

result = []
n = int(sys.stdin.readline().rstrip())
graph = [list(map(int, input().split())) for _ in range(n)]
dp = [[[0, 0, 0] for _ in range(n)] for _ in range(n)]
dp[0][1][0] = 1

# 첫 번째 행 가로이동
for i in range(1, n):
    # 벽이 있으면 break
    if graph[0][i] == 1:
        break
    dp[0][i][0] = 1

for i in range(1, n):
    for j in range(2, n):
        if graph[i][j] == 0:
            dp[i][j][0] = dp[i][j - 1][0] + dp[i][j - 1][2]  #노랑
            dp[i][j][1] = dp[i - 1][j][1] + dp[i - 1][j][2]  #녹색
            # 대각선은 빈 칸 조건 추가적으로 검증
            if graph[i][j - 1] == graph[i - 1][j] == 0:  #파랑
                dp[i][j][2] = dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1] + dp[i - 1][j - 1][2]
print(sum(dp[-1][-1]))

2. 후기

문제에 주어진 그림속에 점화식이 구현되어 있다. 3차원 DP 테이블도 나오는 구나 생각했다.

dp[i][j][0] = 가로 형태인 파이프의 머리가 [i][j]칸에 위치할 수 있는 경우의 수
dp[i][j][0] = ... 세로
dp[i][j][0] = ... 대각선

profile
안녕하세요!

0개의 댓글