백준 1937 욕심쟁이 판다 파이썬 문제풀이 (python 2차원 DP)

문제 보러가기

 

백준 욕심쟁이 판다 파이썬 문제풀이 

14 9 12 10
1 11 5 4
7 15 2 13
6 3 16 8

위의 4x4가 있다고 할 때 어떤 지점에 판다를 놓으면 더 큰 숫자가 있는 방향으로만 이동할 수 있다.

 

nxn에서 탐색한 칸이 최대가 되는 경로와 그 값을 찾는 것인데

상당히 어려워서 더 연습이 필요할 것 같다. 

 

정답 코드

n = int(input())
forest = [list(map(int,input().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]

def recur(y,x):

    if dp[y][x] != 0:
        return dp[y][x]

    for dy, dx in [[1,0],[-1,0],[0,1],[0,-1]]:
    # for dy, dx in [[0,1],[0,-1],[1,0],[-1,0]]:
        ey = y + dy
        ex = x + dx
        if 0 <= ey < n and 0 <= ex < n:
            if forest[y][x] < forest[ey][ex]:
                dp[y][x] = max(dp[y][x], recur(ey,ex) + 1)
    return dp[y][x]

for j in range(n):
    for i in range(n):
        recur(j,i)

print(max(max(row) for row in dp) + 1)

일단 재귀를 이용해서 모든 칸에 대해서 탐색한다.

재귀 안에서는 상하좌우 4방향에 대해 움직인다.

 

주어진 칸 범위를 벗어나지 않아야하고

움직일 곳의 숫자가 더 커야한다. 

 

현재 칸의 dp값과 / 움직일 곳으로 쭉 움직여서 얻은 최종 이동수 + 1

이 두 개 중 큰 값을 현재 dp에 저장한다.

 

여기가 어려운데, recur로 움직일 곳이 또 다음 움직일 횟수에 대해서

더 갈 곳이 없을 때까지 탐색하고 돌아오는 것이다.

 

즉 끝까지 간 결과와 현재 dp중 더 큰 값을 dp에 넣어서 최대값을 넣는 것.

 

주석처리된 for문을 사용하고 원래것을 지우면 탐색 순서만 바뀌는 건데

주석의 코드로 변경하면 런타임 에러가 뜬다.. 이건 왜그런지 모르겠다.

 

이번 문제는 어렵다.. 꼭 다시 풀어봐야겠다.