[DP/백준]1520

백준 1520 DP 파이썬 풀이

| 1트 ~ 7트(실화냐)

def solution(m, n, map_list):

    memoization = [[0 for _ in range(n)] for _ in range(m)]
    memoization[0][0] = 1

    for i in range(0, m):
        for j in range(0, n):
            if i == 0:
                if j!= 0 and map_list[i][j] < map_list[i][j-1]:
                    memoization[i][j] += memoization[i][j-1]
            elif i == m-1:
                if j != 0 and map_list[i][j] < map_list[i][j-1]:
                    memoization[i][j] += memoization[i][j-1]
                if map_list[i-1][j] > map_list[i][j]:
                    memoization[i][j] += memoization[i-1][j]
            else:
                if map_list[i-1][j] > map_list[i][j]:
                    memoization[i][j] += memoization[i-1][j]
                if map_list[i][j-1] > map_list[i][j]:
                    memoization[i][j] += memoization[i][j-1]
                if j != 0 and map_list[i][j-1] < map_list[i][j]:
                    memoization[i][j-1] += memoization[i][j]

    print(memoization[m-1][n-1])


m, n = map(int, input().split())

map_list = []
for i in range(m):
    map_list.append(list(map(int, input().split())))


solution(m, n, map_list)

• 자꾸 이렇게 풀었는데 왜 안되나 생각해봤는데
  위로도 이동할 수 있는거였다 흑흑
• 위 풀이는 위로는 이동 못하고, 좌우하로만 이동할 수 있도록 해놓은 것
• 위로 갈 수 있는 상황이면 위 풀이는 사용할 수 없다

그래서 검색을 해봤는데 dfs + dp를 이용해서 풀 수 있는 듯 하다

| 이후

def solution(m, n, map_list):

    #상하좌우
    direction_list = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    memoization = [[-1 for _ in range(n)] for _ in range(m)] #-1은 도착한 적 없다는 것을 알려줌

    def dfs(x, y):
        nonlocal m, n, map_list, direction_list

        if x == m-1 and y == n-1:
            return 1

        if memoization[x][y] != -1:
            return memoization[x][y]
        else:
            memoization[x][y] = 0
        
        for direction in direction_list:
            after_x , after_y = direction[0] + x, direction[1] + y
            if 0 <= after_x < m and 0 <= after_y < n:
                if map_list[after_x][after_y] < map_list[x][y]:
                    memoization[x][y] += dfs(after_x, after_y)
        
        return memoization[x][y]
    
    print(dfs(0, 0))

m, n = map(int, input().split())

map_list = []
for i in range(m):
    map_list.append(list(map(int, input().split())))


solution(m, n, map_list)

• 킹받는건 pypy3 해야 런타임 에러가 안난다