[백준][DP] 5569. 출근 경로

5569. 출근 경로

 

• 풀이
  • top-down으로 풀기전 백트래킹
  • prev_dir==-1일때 0으로 보내는걸 빼먹어서 시간 많이 뺏김 ㅠㅠ
    • 처음 시작할때는 방향 바꾼게 아니기때문에 changed=0으로 보내야함
  • nx,ny 범위 초과할때 return이 아니라 continue 해주는것 주의
    • 다음 값도 확인해봐야 하므로

w,h=map(int,input().split())

cnt=0
#동, 북
dx=[0,1]
dy=[1,0]
def recur(i,j, prev_dir, changed):
    global cnt
    if i==h-1 and j==w-1:
        cnt+=1
        return
    
    for k in range(2):
        if changed==1 and prev_dir!=k:
            continue
        nx=i+dx[k]
        ny=j+dy[k]

        if nx<0 or ny<0 or nx>=h or ny>=w:
            continue
        if prev_dir==-1 or prev_dir==k:
            recur(nx,ny,k,0)
        else:
            recur(nx,ny,k,1)

recur(0,0,-1,0)
print(cnt)

 

 

• dp 풀이 (top-down)
  • 저장해두어야 하는 값이 없음 -> 뺄 파라미터가 없음 -> 4개 파라미터 = 4차원배열
  • w-1, h-1 위치가 되면 return 1 을 해서 횟수를 1씩 추가할 수 있도록 함
  • ret값에 다 더한 후 dp에 저장해두기

MOD=100000
w,h=map(int,input().split())


#동, 북
dx=[0,1]
dy=[1,0]

dp= [[[[ -1 for _ in range(2)] for _ in range(2)] for _ in range(w)] for _ in range(h)]

def recur(i,j, prev_dir, changed):
    if i==h-1 and j==w-1:
        return 1
    if dp[i][j][prev_dir][changed]!=-1:
        return dp[i][j][prev_dir][changed]
    
    ret=0
    for k in range(2):
        if changed==1 and prev_dir!=k:
            continue
        nx=i+dx[k]
        ny=j+dy[k]

        if nx<0 or ny<0 or nx>=h or ny>=w:
            continue
        if prev_dir==-1 or prev_dir==k:
            ret+= recur(nx,ny,k,0)
        else:
            ret+= recur(nx,ny,k,1)
    
    ret%=MOD
    dp[i][j][prev_dir][changed]=ret
    return dp[i][j][prev_dir][changed]

print(recur(0,0,-1,0))