백준 1937 (1) [백준 1937] 욕심쟁이 판다 문제 1937번: 욕심쟁이 판다 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 이 문제는 DFS의 개념으로 풀이는 가능하지만 DFS만 사용한다면 시간초과로 인해 통과하지 못한다. DFS로 풀며 시간복잡도를 더 줄여야 통과가 가능한 문제이다. 그렇다면 어떻게 더 줄여야 할까? 바로 DP를 이용하면 된다. DP를 사용해서 이미 탐색한 부분이 있다면 진행하지 않고 탐색된 부분의 값을 사용하는 것이다. 코드를 예시로 보자. if (dp[x][y] > 0) { return dp[x][y]; } 위 코.. 이전 1 다음