joonas   9달 전

각 소수에 대해서 1의 변화로 넘어갈 수 있는 인접리스트를 만들고

재귀 돌면서 원하는 소수가 만들어지는 최소로 DP를 했는 데, 이게 계속 틀려서요.

기저케이스가 T에 도착하거나 모든 다음 소수를 탐색했을 경우라 T까지의 최소가 나와야한다고 생각했거든요.

혹시 어떤 경우때문인지 알 수 있을까요?

코드가 너무 길어서 주요 부분만 첨부하겠습니다.

indioindio   9달 전

8179 1733 -> 5

1733 8179 -> 6 을 출력하네요

indioindio   9달 전

아 근데 제출하신거랑 저 코드랑 잘 섞어서 만든 걸로 테스트 한거라서 저 예제를 맞게 출력하실 수도 있을 것 같네요

joonas   9달 전

아.. 소스 자세히 봐주셔서 감사합니다.

제가 어딘가에서 1을 놓쳐서 그렇게 나오는것 같은데, 아예 DP로 불가능한건가 하는 생각이 들어서요.

indioindio   9달 전

음 같은 숫자를 다른 경로로 접근했을 때의 dp테이블의 처리가 제대로 안 돼서 그런것 같기도 하고 잘은 모르겠네요...ㅜㅜ
(이웃에서 목적지까지의 최소거리 + 이웃까지의 거리)의 최소라는 건 아무리 생각해도 맞는 것 같은데 말입니다.

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