메모이제이션으로 풀었습니다.

인접한 맵으로만 갈수 있기때문에 DFS 알고리즘으로 접근하면 됩니다.

dfs로 짜고 메모이제이션까지 해보았는데

dfs 인자로 어떤걸 받나요?

메모이제이션 메모리초과 일어나지 않나요?

좌표 [y,x], 방문했던것 visited... 어머어마한 메모리가 필요하지않나요?

다른 메모이제이션 방법이라도??

최대 500*500이기때문에 메모리가 많이 필요하지 않습니다.

그냥 dp배열을 -1이나 0으로 초기화시켜두고 값이 0보다 클때만 캐싱하게끔 짜면 될거같습니다.

LIS이기도 하니까 어차피 한번 방문했던 지역은 굳이 방문체크를 안해줘도 대나무가 더 적으니 팬더는 안갈겁니다 ㅋㅋ

맞네요....

어차피 한번 방문했던 곳은 논리적으로 chk하지않아도 재방문(사이클)을 하지않겠네요!!!

굳굳 다들 감사해여

AC하긴 했는데, 또 궁금한점이

500*500이 최대인데,

만약 맵이 지그재그로 25만개다 탐색하는 배열이 주어지면, 

재귀함수호출시 스택오버플로우 나지않나요?

그런 입력이 들어오지않아 통과한거같은데..

아마 그럴거같은데요? ㅋㅋㅋ

이 질문에 대한 답변은 고수분께 패스 ㅎㅎ

#include <iostream>
using namespace std;
int main()
{
 int a[16500000];
 cin >> a[0] >> a[1];
 cout << a[0] + a[1];
}

1000번 문제에 위 코드로 제출하면 통과가 됩니다. 스택 공간이 64M으로 잡혀있는 것으로 생각됩니다.

 VS2015 에서 스택 크기를 64M으로 잡고 재귀 함수내에 int 변수 4개 잡고 돌릴경우 26만번정도까지 호출이 되네요.

http://copynull.tistory.com/40

이 문제에서는 스택오버플로우는 절대로 일어나지 않을 것으로 보입니다.

예 감사합니다

헌데, 여타 대회의 기본 스택크기는 1M 로 알고있는데

그런류의 환경에서도 입력이 저렇게 나오는 경우가 있더라고요

그래서 재귀말고 배열다이나믹으로의 풀이법이 있나 해서 혹시나 물어봤어요 ㅎㅎ

있거나 아시거나 짐작되시는분 밑에 댓글 달아주셔요~

예 저도 그래서 궁금해서 테스트 해봤습니다.  저도 스택 오버 플로우를 염두에 두고 힙공간을 이용해서 소스를 제출했는데 그냥 스택공간을 이용해도 괜찮은 것 같네요.

힙공간을 이용한다는게 조금 구체적으로 어떤건지 알수있을까요?

dfs 를 재귀로 작성할경우 묵시적으로 스택을 이용하게 됩니다. 이를 명시적으로 스택을 사용하여 비재귀(non recursive)로 작성이 가능합니다.

저는 STL의 stack을 이용하여 비재귀 DFS를 작성하였습니다.

http://stackoverflow.com/questions/21508765/how-to...

감사합니다.