tddhot2   2년 전

- 방문하는 지점에서 dp로 저장해 두번 같은 경로를 방문하지 않도록 했습니다.

- 문제가 테스트케이스를 1 100000이렇게 두면 프로그램이 죽어버리더군요.. 아무래도 재귀호출을 많이 해서 그런것 같기도 한데 잘 모르겠습니다

- 주어진 TC에 대해서는 정답입니다. 시간내주셔서 알려주시면 많은 도움이 될 것 같습니다~ +_+



zxcv1534   2년 전

숫자가 커서 스택 오버플로우가 난다는 얘기시죠?? 

이 문제는 재귀호출로 풀기엔 무리입니다. 백트래킹 기법을 한 번 알아보세요.

tddhot2   2년 전

아 이문제가 아예 재귀호출로는 안되는 문제인가요??

저는 쟤가 어느 부분을 잘 못해서 그렇게 되는 줄 알아서요 

zxcv1534   2년 전

재귀호출로 안 되는 이유는 답에 도착하기 전에 스택의 허용량을 벗어나기 떄문입니다. 어느 부분을 잘 못 하신 건 아닙니다. 아마 숫자가 적당하다면 답이 충분히 나올 수 있습니다.  한 번 재귀호출이 아닌 한 번에 구할 방법을 생각해보세요. 예를 들자면 만약 도착점이 왼쪽에 있다면 3가지 방향 중 가능한 것은 왼쪽 하나밖에 없겠죠?

그럼 계속 1+f(x-1)을 하지 말고 한 번에 도착점과의 왼쪽 거리만큼을 반환하면 됩니다. 

여기서 백트래킹 사용을 권장하는 이유는 위와 같이 한 번에 구할 수 있게끔 가지치기를 많이 할 수 있기 때문입니다. 

zxcv1534   2년 전

참고로 스택 허용량이 문제라면 큐를 직접 생성하여 BFS 방식으로 풀수도 있습니다. 자동으로 생성되는 스택 허용량보다 동적배열이 더 많은 허용량을 갖거든요.

tddhot2   2년 전

zxcv1534  친절한 설명 너무나 감사드립니다~ 말씀하신대로 적은 범위의 TC에서는 올바른 정답을 내지만 끝에서 끝으로 진행하면 스택호출로 하다보니 안되는 게 맞는 것 같습니다~ BFS방식으로 해결하였습니다 감사합니다!

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