[백준] 17070번 파이프 옮기기 1 (python 파이썬)

문제

17070번: 파이프 옮기기 1

파이프 옮기기 1 / 골드 5

문제 푸는데 걸린 시간

60분... 첫 시도 성공

문제이해를 잘못하여 시간이 많이 소모되었습니다 ㅎ

앞으로는 문제를 꼼꼼히 이해하도록 하겠습니다!

문제를 다르게 생각하기

문제 예시에서 제시하는 (가로,세로,대각선)에서 이동할 수 있는 경우의 수를

 

(가로,세로,대각선)으로 이동할 수 있는 경우로 생각

 

 

가로로 이동할 수 있는 경우

가로로 갈 수 있는 경우 왼쪽블록으로 갈 수 있는 경우중 가로, 대각선에 해당합니다.

세로로 이동할 수 있는 경우

세로로 갈 수 있는 경우 위쪽블록으로 갈 수 있는 경우중 세로, 대각선에 해당합니다.

대각선으로 이동할 수 있는 경우

대각선으로 갈 수 있는 경우 왼쪽위블록으로 갈 수 있는 경우중 가로, 세로, 대각선에 해당합니다.

코드

이를 코드로 구현하면 다음과 같습니다

dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][1] # 가로
dp[i][j][2] = dp[i-1][j][1] + dp[i-1][j][2] # 세로 
if G[i][j-1] == G[i-1][j] == 0 :
    dp[i][j][1] = sum(dp[i-1][j-1]) # 대각선

 

전체 코드

import sys

input  = sys.stdin.readline

n = int(input())
# G = [list(map(int,input().split())) for _ in range(n)]

G = [[0 for _ in range(n)]]
for _ in range(n):
    G.append(list(map(int,input().split())))
dp = [[[0,0,0] for _ in range(n)] for _ in range(n+1)] # 가로 대각선 세로

dp[1][1] = [1,0,0]


for i in range(1,n+1):
    for j in range(1,n):
        if i==j==1:
            continue
        if G[i][j] == 0:
            dp[i][j][0] = dp[i][j-1][0] + dp[i][j-1][1] # 가로
            dp[i][j][2] = dp[i-1][j][1] + dp[i-1][j][2] # 세로 
            if G[i][j-1] == G[i-1][j] == 0 :
                dp[i][j][1] = sum(dp[i-1][j-1]) # 대각선



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

 

잘못된 내용이 있으면 피드백 부탁드립니다!

궁금한 내용이 있으면 언제든지 물어보세요!!!