반응형
SMALL
백준 2437번 저울
-
백준 1937번 욕심쟁이 판다, 2437번 저울 (python)알고리즘 2023. 8. 4. 13:44
욕심쟁이 판다 (1937번) n * n 크기의 대나무 숲에서 판다가 움직이며 대나무를 먹을 때, 이동하는 칸의 대나무가 이전 칸의 대나무보다 많아야지만 이동 할 수 있을 때 판다가 이동 할 수 있는 칸의 수의 최대값을 출력합니다. 판다가 처음 이동을 시작하는 칸도 주어지지 않았기 때문에 모든 칸을 시작점으로 생각하여 이동을 해봐야 된다고 생각했습니다. 하지만, 모든 칸에서 이동 할 수 있는 칸의 수를 세는 것은 시간이 오래 걸릴 것으로 예상했습니다. 그래서, 각 칸마다 해당 칸에서 이동 할 수 있는 최대 칸의 개수를 저장해서 이전에 방문했던 칸이라면 다시 순회하지 않도록 했습니다. dp 문제는 이전의 어떤 로직에 의해 발견된 값과 현재 다시 이 칸을 방문했을 때의 값을 비교해서 다른 값을 채워넣는 식의 ..