pica4500   2년 전

최소 이동횟수를 계산할때는 한번 이동했던점을 다시 방문하면 최소가 아니라는 점에서

dp를 이용하여 해결하려고 했습니다.

f, b한 부분에 경찰서가 있는지, 범위안에 들어있는지, 방문을 했는지 확인후 다시 탐색을 하였습니다.

f나 b가 0이어도 한번 호출되었을때도 그 위치에 INF가 들어가있어, bug found가 될텐데.. 어느부분이 틀린지 잘 모르겠습니다 ㅠㅠ

dotorya   2년 전

cache 배열을 이용해서 이전에 계산했던 결과를 저장하시려고 하셨던 것 같은데, 몇 가지 문제점이 있습니다.

1. !cache[pos-b], !cache[pos+f]는 사용해서는 안되는 조건입니다.

최초에 pos-b나 pos+f를 방문했던 방법이 최적의 방법보다 비효율적이었을 수도 있지 않을까요?

2.  (좀 더 어렵지만) 비슷한 이유로, 지금 cache 배열에 계산 결과를 미리 저장해 두는 방식은 잘못되었습니다.

count 변수를 별도로 사용하지 않고, 'find(pos) : pos에서 d까지 이동할 수 있는 최소 횟수' 등으로 정의하는 방법을 생각해 보세요.

3. (?) 이건 해야하는지 잘 모르겠는데, S나 D에 경찰서가 있는 경우가 있을 수도 있을 것 같습니다.

문제를 내신 분이 좋으신 분이라면 없을 것 같지만, 아닐 수도 있으니까요..


kdk8361   2년 전

감사합니다. 덕분에 힌트잡고 풀었습니다.

pica4500   2년 전

감사합니다. 모든 가중치가 같다는 점으로 새로운 알고리즘으로 해결해봐야겠어요!

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