hsna7024   4년 전

안녕하세요.

계단오르기 문제 질문하려고 합니다.

알고리즘은 i번째 계단을 밟았을 때의 최대값 안밟았을 때의 최대값 2개를 저장해서 풀었습니다.

  dp[i][0] = i번째 계단을 밟지 않았을 때의 최대값

  dp[i][1] = i번째 계단을 밟았을 때의 최대값

계단을 밟지 않았을 때는 i-1 번째의 값중 최대값을 저장하고 계단을 밟을 경우에는 연속된 3개의 계단을 밟지 않도록 조건을 걸었습니다. i-2 번째 계단을 밟았으면 i - 1 계단을 밟지 않고 i -1 번째 계단을 밟으면 i - 2 계단을 밟지 않도록 하였습니다. 점화식은 다음과 같습니다.

  dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]);
  dp[i][1] = Math.max(dp[i-2][0] + stair[i-1], dp[i-2][1]) + stair[i];

첫번 째 계단과 두번 째 계단은 따로 초기화를 하였습니다.

이와 같은 풀이로 포도주시식 (2156문제) 믄제를 해결해서 이상없이 풀 수 있을 것이라 생각했는데

틀렸다고 결과가 나오네요.

기존에 있던 질문글을 검색해서 반례 테스트를 해봤는데 아직 틀린 것을 못찾았습니다.

혹시 풀이에 문제가 있거나 반례를 알고 계시면 조언 해주시길 부탁드리겠습니다.

감사합니다.


simm4256   4년 전

1) dp[0][0]이 초기화되지 않았습니다.

2) dp[i][0]은 dp[i-1][0]이 될 수 없습니다. 문제 조건에 한번에 세 계단을 뛰어넘지는 못한다고 명시되어있습니다.

따라서 dp[i][0] = dp[i-1][1] 이 됩니다.


두개만 수정하시면 AC가 나오실겁니다.

hsna7024   4년 전

simm4256님 감사합니다. 해결했습니다.

계속 고생했었는데 착각하고 있었네요 ㅠㅠ

1)은 dp[0][0] 은 항상 0이기 때문에 따로 초기화하지 않았고

2)수정하니 바로 정답 나왔습니다.

덕분에 해결 했습니다.

감사합니다.

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