계단오르기 dp 질문이요~. 뭐가 문제일까요? 아무리 고쳐봐도 계속 틀렸습니다 가 나옵니다.


etaehyun4   5달 전

점화식이 잘못되었습니다. visited[steps] 는 steps가 같으면 나머지 상태는 같다는 가정이 있어야 하는데, 연속 1계단으로  steps를 도달한 경우와 연속 2계단으로 steps를 도달한 경우 추후 밟을 수 있는 값이 다릅니다

네???? 뭔뜻 인가요???

etaehyun4   5달 전

위의 소스대로라면 0->1->3->4->.. 순서로 처리가 되겠죠?

그럼 3번에 있을 때 visited[3] 은 값이 채워지고 말 것입니다.

하지만 0->2->3 이라는 경우도 있는데 go함수에서 이 경우에 도달 했을 때 0->2->3-> (4->...) 의 경우는 처리하지 못해 그 상태에서 visited[3]은 올바른 답이 되지 못합니다. 하지만 return visited[3] 을 호출하겠죠?

이 문제에선 점화식이 1차원으로 풀리지 않습니다. 조금 더 고민해보시기 바랍니다.


더불어, 바닥 0일 땐 점수가 0이어야 하는데, 점수 입력을 0번부터 받아 위의 소스는 예제 데이터도 나오지 않는 것 같습니다

감사합니다. 다시 풀어볼게요.....ㅠㅠ....

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