17070: 파이프 옮기기 1

문제 링크

17070: 파이프 옮기기 1

구현 방식

• 3차원 dp table을 이용해 풀어주었다

  • dp[i][j][0]는 가로 파이프 놓는 경우의 수, dp[i][j][1]은 세로 파이프 놓는 경우의 수, dp[i][j][2]는 대각선 파이프 놓는 경우의 수

  • 기저: 0행먼저 순회하면서 board[0][i]의 값이 0이라면 dp[0][i][0] = dp[0][i-1][0]으로 갱신해줌

• dp의 값은 파이프 끝의 위치를 기준으로 생각해주어야한다

  • for i in range(1, N): for j in range(1, N)를 순회하면서 dp table을 갱신해준다
    • 현재 위치의 board 값 (board[i][j])이 0인 경우, 가로, 세로 파이프를 놓을 수 있다
      -> 가로파이프는 (좌)위치의 가로파이프, 대각선파이프로부터 놓을 수 있다
      -> 세로파이프는 (상)위치의 세로파이프, 대각선파이프로부터 놓을 수 있다
    • (현재 위치, 상, 좌)의 위치의 board 값이 0인 경우, 대각선 파이프를 놓을 수 있다
      -> 대각선파이프는 (좌상)위치의 가로파이프, 세로파이프, 대각선파이프로부터 놓을 수 있다

코드

import sys

N = int(sys.stdin.readline()[:-1])
board = []
for n in range(N):
    board.append(list(map(int, sys.stdin.readline()[:-1].split())))

dp = [[[0] * 3 for _ in range(N)] for _ in range(N)] #파이프 끝의 위치

dp[0][1][0] = 1
for i in range(2, N): # 0행 먼저 채워주기
    if board[0][i] == 0: dp[0][i][0] = dp[0][i-1][0]

for i in range(1, N):
    for j in range(1, N):
        if board[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 board[i][j] == 0 and board[i-1][j] == 0 and board[i][j-1] == 0: #대각선 파이프 놓을 수 있는 경우
            dp[i][j][2] = dp[i-1][j-1][0] + dp[i-1][j-1][1] + dp[i-1][j-1][2]

print(dp[N-1][N-1][0] + dp[N-1][N-1][1] + dp[N-1][N-1][2])

결과