ingyo   2년 전

안녕하세요!

점프 문제를 푸는데 자꾸 시간초과가 나서 질문을 올립니다.

dfs로 경로를 탐색해서 목적지에 도달할때마다 하나씩 카운트하는식으로 짯는데, 이거보다 효율적이게 짤수있는건지 궁금합니다.

dp로만 풀리는걸까요 ㅠㅠ

sgchoi5   2년 전

N 이 100 정도 되기 때문에 dfs 로는 시간 초과 해결이 안 됩니다.

dfs 기본 코드에 dp 기법만 적용한다고 보시면 됩니다.

즉, dfs 수행 시에 i, j 지점을 여러 번 지나갈텐데, i, j 지점에 대한 가지수를 한 번 계산해두면 dfs 를 더 안하고 그냥 그 값을 return 한다고 보면 됩니다.

Code pattern (문제해결전략 참조) 입니다

dp%2Btopdown%2Btemplate.PNG




ingyo   2년 전

아하!

우연히 블로그도 들어가봤는데 좋은글이 많네요 ㅎㅎ 감사합니다!

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