selgun05   5년 전

다른분들 코드 알고리즘을 몇개 읽어봤는데 제가 조금 특이하게 푼거 같아서.. 코드 설명하자면요...

DP[0][0]은 1로 두고, 초기값은 -1로 두고, M-1, N-1에서 fine함수를 호출합니다

호출된 좌표에선 호출당한 방향 + 유효하지 않은 좌표(0미만, n,m이상) + 내리막이 아닌 방향에서 DP값을 가져와서 더합니다.(3방향 값을 각각 v1, v2, v3으로 받아서 DP에 저장, 유효하지 않은 방향값은 0이 됨) 방향이 유효한데 좌표의 DP가 없다면 fine 함수를 재귀호출해서 그 좌표 DP값을 recusive하게 계산합니다.

내림차순이 반복될 수 없기 때문에 결국 0,0좌표의 DP값(1)이 참조되면서 DP가 다 계산됩니다.

근데 여기서 DP값이 있는지 없는지 판단할 때, 처음엔 DP 초기값을 0으로 두고 주석으로 한 코드 처럼 0인지 확인(DP값 없는지)하고 fine호출하고 경로에 없는 좌표면 -1을 저장했는데 시간초과가 났습니다..

고민하다가 이건 무한루프가 돌수가 없다고  판단하고 설마하고 초기값을 -1로 두고 경로에 없는 좌표면 0으로 두었는데 바로 성공하네요.. 

DP초기값(계산 안됨) 0, 값 없음(경로 없음) = -1 -> 시간 초과

DP초기값 (계산 안됨) -1, 값 없음(경로 없음) = 0-> 성공 입니다.

다이나믹 프로그래밍이 메모이제이션으로 시간을 확 줄이는 것으로 알고 있습니다.

메모이제이션이 잘 작동되고 있다면 초기값 비교하는 시간정도는 무시될 정도로 시간이 확 줄거라고 생각했는데

초기값이 다른 것 때문에 시간초과가 납니다.

아니면 혹시 제가 무한루프를 발견하지 못한 걸까요?

알려주시면 감사하겠습니다. ㅠㅜ



댓글을 작성하려면 로그인해야 합니다.