알고리즘 풀이/백준(Boj)
백준(BOJ) 1937번 욕심쟁이 판다
100win10
2019. 10. 27. 01:37
문제 : https://www.acmicpc.net/problem/1937
1937번: 욕심쟁이 판다
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이
www.acmicpc.net
풀이 :
0,0부터 n n까지 모든 경우의 수를 조사하여 최대 길이를 찾아야 한다.
이때 한 y,x에서의 길이는 이미 구해진 인접한 상하좌우의 길이에 +1만 해주면 되므로 메모이제이션을 이용하자.
코드 ( C++ )
