-
백준(BOJ) 1937번 욕심쟁이 판다알고리즘 풀이/백준(Boj) 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++ )
'알고리즘 풀이 > 백준(Boj)' 카테고리의 다른 글
백준(BOJ) 17070번 파이프 옮기기 1 (31) 2019.10.31 백준(BOJ) 3085번 사탕 게임 (0) 2019.10.27 백준(BOJ) 2169번 로봇 조종하기 (3) 2019.10.27 백준(BOJ) 14225번 부분수열의 합 (31) 2019.10.25 백준(BOJ) 2151번 거울 설치 (31) 2019.10.22