-
백준 1937 python백준/다이나믹 프로그래밍 2023. 5. 1. 14:45
문제
https://www.acmicpc.net/problem/1937
풀이
- DFS 알고리즘을 이용한다.
- 시간 초과를 피하기 위해 방문했던 V 배열은 기존의 순회 정보를 이용한다. (다이나믹 프로그래밍)
import sys sys.setrecursionlimit(10**6) [n],*I=[list(map(int, x.split())) for x in [*open(0)]] V=[[0]*n for _ in range(n)] def dfs(x,y): if V[x][y]: return V[x][y] V[x][y]=1 for nx,ny in [[x-1,y],[x,y-1],[x,y+1],[x+1,y]]: if 0<=nx<n and 0<=ny<n and I[x][y]<I[nx][ny]: V[x][y]=max(V[x][y], dfs(nx,ny)+1) return V[x][y] o=0 for i in range(n): for j in range(n): o=max(o,dfs(i,j)) print(o)
참조
https://kyun2da.github.io/2021/04/04/panda/
후기
- 문제 풀이 알고리즘이 dfs와 dp인 것은 파악했으나, 역순으로 dp 배열을 return하는 과정에서 시간을 사용했던 문제.
- PyPy3로 제출하면 메모리 초과가 발생하므로, Python3로 제출해야 함.
'백준 > 다이나믹 프로그래밍' 카테고리의 다른 글
백준 5582 nodejs (0) 2023.02.16 백준 7579 nodejs (0) 2023.02.12 백준 1256 nodejs (0) 2023.02.08 백준 2098 nodejs (0) 2023.02.06 백준 1014 nodejs (0) 2023.02.03