17070 파이프 옮기기 1

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

#dp

17070번: 파이프 옮기기 1

#17070 파이프 옮기기 1

 

#내코드 ( 시간초과 )

from sys import stdin

input=stdin.readline
#스탠다드 입력
def solution(d,r,c):
    global answer
    if r==n-1 and c==n-1:
        answer+=1
    '''
    1. d는 이전의 파이프 방향

    2. 파이프의 조건 대각선일때 [y+1][x] [y+1][x+1] [y][x+1] 다 비어져 있고 그냥 일자로 갈때는 방향에 따라 거기에 없어야 하며

    3. n-1값을 넘어서는 안된다.

    4. 예를 들어 d=1 row 이면 house[y][x+1]=1 해주고 돌리고 다음에 0으로 바꿔줘야 다음으로 넘어갈 수 있음
    '''
    if d==0:
        if not (r==n-1 or c==n-1) and not (house[c+1][r+1] or house[c+1][r] or house[c][r+1]):
            house[c+1][r+1]=1
            solution(0,r+1,c+1)
            house[c+1][r+1]=0
        if r!=n-1 and not house[c][r+1]:
            house[c][r+1]=1
            solution(1,r+1,c)
            house[c][r+1]=0
        if c!=n-1 and not house[c+1][r]:
            house[c+1][r]=1
            solution(2,r,c+1)
            house[c+1][r]=0
    if d==1:
        if not (r==n-1 or c==n-1) and not (house[c+1][r+1] or house[c+1][r] or house[c][r+1]):
            house[c+1][r+1]=1
            solution(0,r+1,c+1)
            house[c+1][r+1]=0
        if r!=n-1 and not house[c][r+1]:
            house[c][r+1]=1
            solution(1,r+1,c)
            house[c][r+1]=0
    if d==2:   
        if not (r==n-1 or c==n-1) and not (house[c+1][r+1] or house[c+1][r] or house[c][r+1]):
            house[c+1][r+1]=1
            solution(0,r+1,c+1)
            house[c+1][r+1]=0
        if c!=n-1 and not house[c+1][r]:
            house[c+1][r]=1
            solution(2,r,c+1)
            house[c+1][r]=0
n=int(input())
house=[list(map(int,input().split())) for i in range(n)]
house[0][0]=1
house[0][1]=1
answer=0
solution(1,1,0)
if answer:
    print(answer)
else:
    print(0)

#진짜 해석느낌으로 적어봤는데 시간초과가 나왔다 하하하핳ㅎ. 절망적이게도 답지를 보게 되었다.

#내 생각은 하나하나 길을 따라가는 것이였다 하지만 이는 dp를 사용한것과는 시간이 차원이 다르기에 틀렸다는걸 이미 #알고있었고, dp를 사용해서 풀려고 해도 생각이 나지 않아 힘들었다 고로 답지행..

 

#답지

 

# 17070 파이프 옮기기 1 dp 사용

from sys import stdin
input=stdin.readline

# 스탠다드 인풋

 

n=int(input())
pipe=[list(map(int,input().split())) for i in range(n)]
# 기본 입력

 

dp=[[[0]*3 for i in range(n)] for i in range(n)]
# dp 생성 가로 세로 대각선

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

# dp 초기값 처음에 0 0 과 0 1 이 연결 되어있으므로

def up_pipe(x,y):
    try:
        if pipe[y][x] or pipe[y-1][x]:
            raise
        up=dp[y-1][x]
    except:
        up=None
    return up

# 위쪽 파이프 탐색과 현재 파이프 탐색 여기서 중요한건 이미 파이프를 보내놓고 이전것을 생각한다는 것이다. 이것이

# 이 dp의 핵심이다. 

def left_pipe(x,y):
    try:
        if pipe[y][x] or pipe[y][x-1]:
            raise
        left=dp[y][x-1]
    except:
        left=None
    return left

# 왼쪽 파이프와 현재 파이프 탐색

def diagonal_pipe(x,y):
    try:
        if pipe[y][x] or pipe[y-1][x-1] or pipe[y][x-1] or pipe[y-1][x]:
            raise
        diagonal=dp[y-1][x-1]
    except:
        diagonal=None
    return diagonal

# 대각선으로 오기 위해서는 위쪽 왼쪽 대각선뒤 다 확인해야됨.

for y in range(n):

# 0 0 , 0 1로 시작 고로 y시작은 0
    for x in range(2,n):

# 1부터 시작하고 가로로 시작했기 때문에 어떻게 해도 2부터 시작함 ( 대각선, 가로)
        if pipe[y][x]==1:
            continue
# y x가 벽일경우 스킵하고 다음으로
        up=up_pipe(x,y)
        if up:
            dp[y][x][1]=up[2]+up[1]
#세로로 파이프를 두려면 이전것이 대각선, 세로로 끝났어야 한다.
        left=left_pipe(x,y)
        if left:
            dp[y][x][0]=left[0]+left[2]
#위와 같음
        diagonal=diagonal_pipe(x,y)
        if diagonal:
            dp[y][x][2]=diagonal[2]+diagonal[1]+diagonal[0]
#대각선은 다 가능

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

#생각하니깐 너무 간단해서 화가 난다. 생각을 잘해야된다. y와 x 그리고 3개의 인덱스를 이용해서 dp를 작성한 후 약간 피보나치처럼 처리를 해주는 간단한 문제였다.