[일반] 뉴비 질문 하나만 할게요...

뱀과 사다리 문제입니다.

바텀업 DP로 안되는 건 알겠는데 아무리 생각해도 제가 작성한 탑다운 DP의 반례를 잘 못찾겠습니다...

한번만 도와주시면 감사하겠습니다.

사이클이 발생할 수 있기 때문이에요

EN_SA(encludingsalt) 2023-12-15 17:01

답글

그게 잘 이해가 안 돼요...정말 죄송하지만 반례하나만 들어주실 수 있을까요??

익명(147.47) 2023-12-15 17:02

답글

예를 들어 5번 칸에 처음으로 방문한 시점에서 점화식을 따라 6번칸을 간다고 생각해봅시다. 그런데 6번칸에 5번으로 돌아가는 뱀이 있다면 5번 칸의 dp 값을 참조할 겁니다. 구현 상 dp[5] = 987어쩌구로 대입되어있는 상태니 잘못된 값을 참조하게 되는거죠

EN_SA(encludingsalt) 2023-12-15 17:07

답글

근데 그러면 6번을 지나는 길은 항상 최적의 방법이 아니어서 결국 5번에서 다른 길로 가는 경우에 의해 dp[5]가 덮어씌워지지 않나요?? 계속 여쭤봐서 죄송해요 ㅠㅠ

익명(147.47) 2023-12-15 17:10

서울대 반갑고

익명(39.7) 2023-12-15 19:00

댓글 5