[BOJ]1937 욕심쟁이 판다- 파이썬

https://www.acmicpc.net/problem/1937
DP로 풀수 있는 문제였다. (dfs로는 시간초과엿기 때문에)
먼저 입력받은 대나무의 배열을 내림차순으로 정렬했다.

코드 (Language)

N = int(input())

dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

boards = []
indexLists = []
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]

for i in range(N):

    tempList = (list(map(int, input().split(" "))))
    for j in range(len(tempList)):
        indexLists.append([tempList[j], i, j])
    boards.append(tempList)

indexLists.sort(reverse=True)

for indexList in indexLists:
    currentValue = indexList[0]
    x = indexList[1]
    y = indexList[2]
    maxValue = 0
    for i in range(4):
        nx = x+dx[i]
        ny = y+dy[i]
        if 0 > nx or nx >= N or 0 > ny or ny >= N:
            continue
        if boards[nx][ny] > currentValue:
            if dp[nx][ny]+1 > maxValue:
                maxValue = dp[nx][ny]+1
    dp[x][y] = maxValue

ans = 0
for d in dp:
    if max(d) > ans:
        ans = max(d)

print(ans+1)

접근 방식

[[3,4] ,…..

그리고 가장 대나무가 많은 곳 부터 차례로 사방을 살펴보고 자신보다 큰 수의 DP값 +1을 dp에 저장했고

마지막으로 DP에서 가장큰 값을 출력하면 된다