[BAEKJOON] 1937 욕심쟁이 판다

#include <iostream> #include <vector> #include <fstream> #include <algorithm> using namespace std; int bamboo_count; vector<vector<int>>bamboo; vector<vector<int>>cache; int eating_bamboo(int x, int y, int before_bamboo) { if (bamboo[x][y] <= before_bamboo) return 0; int&ret = cache[x][y]; if (ret != 0) return ret; if (x - 1 >= 0) ret = max(ret, eating_bamboo(x - 1, y, bamboo[x][y]) + 1); if (y - 1 >= 0) ret = max(ret, eating_bamboo(x, y - 1, bamboo[x][y]) + 1); if (x + 1 < bamboo_count) ret = max(ret, eating_bamboo(x + 1, y, bamboo[x][y]) + 1); if (y + 1 < bamboo_count) ret = max(ret, eating_bamboo(x, y + 1, bamboo[x][y]) + 1); return ret; } int main() { int answer = 0; cin >> bamboo_count; bamboo = vector<vector<int>>(bamboo_count, vector<int>(bamboo_count)); cache = vector<vector<int>>(bamboo_count, vector<int>(bamboo_count, 0)); for (int j = 0; j < bamboo_count; j++) for (int k = 0; k < bamboo_count; k++) cin >> bamboo[j][k]; for (int j = 0; j < bamboo_count; j++) for (int k = 0; k < bamboo_count; k++) answer = max(answer, eating_bamboo(j, k, -1)); cout << answer << endl; }

일단 top down방식 이걸 알고나서 부터 줄곧 이 방식만 쓴다 최고 짱짱

암튼 이 문제는 결국 cache에  x,y였다면 그 지점부터 시작해서 그 지점보다 큰 수로 갈 수 있는 max값을 저장하는 것이다.

분명 그렇게 짰는데 하나도 안돌아갔다.

처음에는 +1을 안해주고 max도 안해주고 무작정 더했다 (모든 경우의 수를 구하듯..)

하지만 그렇게 하는것을 아니라는 것을 빨리 깨닫고

+1을 더해주는 걸로 변경하였고 max값을 저장하였다.

그런데!!! 돌아가지 않는 것이다.

왜지? 왜 안돌아가지

아..등호가 빠졌었다.

전보다 같거나 작으면 return 0을 하는 건데

작을 때만 한것이다..

후..

그래서 결국 정답이 떴다..