pineleaf1215   4년 전

우선 음

메모제이션을 사용했고, memo[][]이차원 배열에, 그 경로까지의 최솟값을 구했습니다.

근데 여기서 dp랑 조금 햇갈리는 부분이. c라는 지점까지의 최소의 경로를  a,b를 거치면서 바로 알수 있는거 아닌가요?

근데 이 문제는 끝까지 가봐야 알수 있는거 같은데 그렇다면 끝까지 갓봐야 최솟값을 알수 있으니까. 

다시오는 백트렉킹이 아닌가요?


그렇다면 결론은 순수 dp는 아닌 여러 개념이 섞인건가요..?


djm03178   4년 전

음... 어떻게 하신 건지 정확히는 모르겠지만, 이 문제를 순수(?) dp로 풀면 딱 linear 타임에 해결이 됩니다. 1000 * 3 * (가벼운 상수) 정도라 C나 C++이라면 압도적 0ms가 뜨게 할 수 있는데, 12ms가 뜨셨네요. 아무래도, 왔다갔다 하는 과정이 계속 있으니까 좀 느린 방법인 것 같네요.

pineleaf1215   4년 전

음 해답을 보니까 알겠더군요..

mem[p][2] = min (mem[p-1][0]+A[p][2],mem[p-1][1]+A[p][2])

뭐 이런 거 같은데 dp에서 min,max를 이용해서 많이 하는 군요 ㅜㅠ

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