1520번 파이썬

 

처음에 아래 코드처럼 모든 배열을 다 돌아서 dp만을 이용하는 방식으로 풀려고 했는데 예제에서 20에서 17로 내려갈때 20은 2로 되어있는데 17은 1로 되어있어서 문제 해결이 되지 않았다. 그래서 다른 방식으로라도 해답을 구하긴 했는데 다른 예외 경우가 있는지 틀렸다고 떠서 다른 사람의 방식을 ㅂ참고했다..! 

import sys
input = sys.stdin.readline
m,n=map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(m)]
p = [[0 for _ in range(n)] for __ in range(m)]
p[0][0]=1
dx=[1,-1,0,0]
dy=[0,0,1,-1]

for row in range(m):
  for col in range(n):
    if row==m-1 and col==n-1:
      continue
    for i in range(4):
      r=row+dx[i]
      c=col+dy[i]
      if 0<=r<m and 0<=c<n and ary[row][col] > ary[r][c]:
        p[r][c]+=p[row][col]
print(p[m-1][n-1])

대부분의 사람들이 dp랑 dfs방식을 섞어서 썼다. 첨에 dfs 쓰면 시간 초과가 뜰것 같아서 생각안해봤는데 이런 방식이 되는줄 몰랐다 ,,,

사람들은 dfs를 끝에서부터(도착지) 출발지까지 값을 끌고 올라오는 방식을 이용했다..!

방문을 했을 경우엔 값을 0으로 바꾸고

내리막길로 내려가는 for문을 돌려서 만약 다음에 내리막길이 있을 경우 dfs를 현재 dp에 추가하는 방식을 이용했다.

중간에     p[r][c]!=-1:     이 구문은 해당 인덱스를 이미 방문했을 경우의 처리이다!

이렇게 하면 출발지 값에 도착지까지 가는 경우의 수가 저장된다..!

 

import sys
input = sys.stdin.readline
m,n=map(int,input().split())
ary = [list(map(int,input().split())) for _ in range(m)]
p = [[-1 for _ in range(n)] for __ in range(m)]
dx=[1,-1,0,0]
dy=[0,0,1,-1]
def dfs(r,c):
  if r==m-1 and c == n-1:
    return 1
  if p[r][c]!=-1:
    return p[r][c]
  p[r][c]=0
  for i in range(4):
    row = r+dx[i]
    col = c+dy[i]
    if 0 <= row < m and 0 <= col < n and ary[row][col] < ary[r][c]:
      p[r][c]+=dfs(row,col)
  return p[r][c]
print(dfs(0,0))