본문 바로가기

19371

[BOJ] 1937 : 욕심쟁이 판다 문제 링크 1937번: 욕심쟁이 판다 (acmicpc.net) 풀이 문제를 보면 일단 DFS문제라는 것을 알 수 있다. 시작점에서 상하좌우 중 범위를 벗어나지 않으면서 현재 지점보다 값이 크면 그 지점을 방문한다. 그렇게 해서 더 이상 이동할 수 없을때 까지 도달했을 때 그 깊이 중 가장 큰 값을 찾는 문제이다. 그런데 모든 점에서부터 출발해서 최대값을 찾으면 될까?? 당연히 아니다. 그렇게 하게되면 이미 방문했던 지점을 시작점으로 같은 경로를 재탐색 하게되는 경우가 발생하기 때문에 시간초과가 난다. 그럼 어떻게 해야할까? DP를 이용해서 재방문을 하지 않도록 해야한다. 예제를 보자 4 14 9 12 10 1 11 5 4 7 15 2 13 6 3 16 8 (1,1)을 출발점으로 했을 때 주변에 자신(14.. 2022. 3. 1.

이전 1 다음

티스토리툴바