songmin9813   2년 전

처음 보자마자 생각했던 알고리즘이 '한 칸씩 올라가면서 각 칸에 도착할 수 있는 주사위의 최소 굴림수를 저장하자!'라는 느낌으로 접근했는데 틀렸습니다가 나왔습니다. 이후 BFS를 사용하여 풀어야함을 알게되었고, 현재는 AC를 받은 상태입니다.


BFS로 풀면서 추상적으로 'DP는 사용하면 안 되는 거구나'라고만 알게 되었지, 이게 정확히 어떤 이유로 DP로 풀면 안 되는 문제인지는 머릿속에 감이 잡히지 않습니다. 그 이유를 알려주실 분 있으신가요?


혹 가능하다면 이 문제를 어떤식으로 변형했을 때 DP로 풀수 있는지도 알려주신다면 이해에 많은 도움이 될 것 같습니다. 감사합니다.

ksi4495   2년 전

뱀을 타고 내려가야 이득인 경우가 있기 때문입니다.

chansol   2년 전

윗 분이 말씀해주신 것처럼, 보통 한쪽 방향으로 이동해서 사이클이 생기지 않는 그래프(DAG)에서 DP를 사용하기 편합니다.

그런데, 이 문제는 올라갔다가 내려오는 과정에 한쪽 방향으로만 이동하지 않습니다. 그래서, DP를 사용하기 어려운 문제인 것 같습니다.

songmin9813   2년 전

말로는 설명하기 어려웠는데, 확실히 사이클이 생기지 않는 그래프/단방향에서 DP를 사용하기 편할 것 같네요. 모두 빠르고 친절한 설명 감사합니다.

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