반응형
메모이제이션
-
BOJ) 욕심쟁이 판다(1937, JAVA)알고리즘/백준 2020. 8. 25. 17:54
욕심쟁이 판다 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 풀이 메모이제이션을 활용한 dp문제다. 생각보다 너무 어려웠다. 알고리즘을 조금 쉬었다가 메모이제이션을 적용시켜서 dp를 활용하려니까 감이 잡히지 않았다. 그래서 다른 사람들의 풀이를 보면서 이해했다. 먼저, out of index를 방지해줄 inInArea 메소드와 움직일 수 있는 조건인지 확인하는 canMove 메소드를 만들었다. 이후, dfs 메소드인 findBamboo를 통해 문제의 조건에 따라 움직이며 최대 날을 구했다. 해당 위..