BOJ 17069 파이프 옮기기 2(python 3)

 

파이프 옮기기 2의 코드는 python 3으로 제출해도 됩니다.

 

파이프 옮기기 2는 1과 다르게 시간 제한이 1초에서 0.5초로 줄어들었고, N의 범위가 3~16에서 3~32로 늘어났습니다.

 

이 문제는 DP로 풀 수 있습니다.

이번엔 칸에 칠해진 색깔과 파이프의 색깔을 살펴봐야합니다.

 

노란색 파이프(→)처럼 놓일려면 아래 두 방법중에 하나를 이용해야 합니다.(배열 좌표는 x, y라고 가정)

1) x, y-1인 노란색 파이프(→)

2) x, y-1인 파란색 파이프(↘)

 

파란색 파이프(↘)처럼 놓일려면 아래 세 방법중에 하나를 이용해야 합니다.

1) x-1, y-1인 노란색 파이프(→)

2) x-1, y-1인 파란색 파이프(↘)

3) x-1, y-1인 초록색 파이프(↓)

 

초록색 파이프(↓)처럼 놓일려면 아래 두 방법중에 하나를 이용해야 합니다.

1) x-1, y인 파란색 파이프(↘)

2) x-1, y인 초록색 파이프(↓)

 

각각 파이프처럼 놓일려면 위에 나온 방법을 각각 전부 더해주면 됩니다.

 

 

 

 

 

 

 

 

 

 

 

 

완성된 코드는 이렇습니다.

n = int(input())
D = [[*map(int, input().split())] for _ in range(n)]
S = [[[0] * 3 for _ in range(n)] for __ in range(n)]
S[0][1][0] = 1
for i in range(2, n):
    if D[0][i] == 1: break
    S[0][i][0] = 1
for i in range(1, n):
    for j in range(2, n):# → 0 ,↘ 1, ↓ 2
        if D[i][j] == 0:
            S[i][j][0] = S[i][j - 1][0] + S[i][j - 1][1]
            S[i][j][2] = S[i - 1][j][1] + S[i - 1][j][2]
            if D[i - 1][j] == D[i][j - 1] == 0:
                S[i][j][1] = sum(S[i - 1][j - 1])
print(sum(S[n - 1][n - 1]))