https://www.acmicpc.net/problem/1937
1937번: 욕심쟁이 판다
n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에
www.acmicpc.net
DP를 활용하여 풀이하였습니다. 대나무의 수가 증가하는 방향으로 움직어야합니다. 반대로, 대나무의 수가 감소하는 방향으로 움직여도 됩니다. 저는 대나무의 수를 큰 수로 내림차순으로 정렬을 하고 현재 대나무의 위치에서 사방탐색을 진행해주면 DP 배열을 채워주면 됩니다. 만약, 현재 대나무의 수보다 작은 대나무 숲이 인접해있다면 현재 대나무 숲에서 이동이 가능합니다. 따라서, 현재까지 이동가능 한 경로의 길이와 다음 이동할 위치의 경로 길이를 비교하여 더 큰 값을 택해주면 됩니다.
import sys
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline
n = int(input())
board = [
list(map(int, input().split()))
for _ in range(n)
]
pos = [
(y, x) for y in range(n) for x in range(n)
]
pos.sort(key=lambda x: board[x[0]][x[1]], reverse=True)
dp = [
[1] * n
for _ in range(n)
]
dys = [0, 1, 0, -1]
dxs = [1, 0, -1, 0]
def inRange(y, x):
return 0 <= y < n and 0 <= x < n
for y, x in pos:
cur = board[y][x]
for dy, dx in zip(dys, dxs):
ny = y + dy
nx = x + dx
if inRange(ny, nx):
next_num = board[ny][nx]
if cur > next_num:
dp[ny][nx] = max(dp[ny][nx], dp[y][x] + 1)
print(max([
dp[i][j] for i in range(n) for j in range(n)
]))