아래 예시와 같은 경우가 있다고 가정해봅시다.
위 코드는 가장 마지막 계단인 20을 밟은 뒤에 그 다음 계단들의 값인 10과 15에 대해서만 생각해보고, 그 뒤에 100과 150이 있다는걸 알지 못하기 때문에 15를 밟는 쪽으로 가게 됩니다.
위 방법을 잘 수정해서 어찌 하다보면 문제를 풀수도 있겠지만, 저는 어떻게 수정해야할지 잘 모르겠네요. 그래서 위와같이 순서대로 읽어가면서 정답에 값을 더해주는 방법 대신 다이나믹 프로그래밍으로 푸는 걸 추천드립니다.
sminhyuck 4년 전
마지막 계단은 항상 밟아야 하기에 마지막 계단은 밟은 상태로 그 앞의 계단 부터 움직이도록 하였습니다.
COUNT를 이용해 1이면 이전 계단을 밟은 상태로, 현재 계단 또는 앞의 계단 중 큰 값을 밟도록 합니다.
COUNT가 0 이면, 이전 계단을 밟지 않은 상태로 현재+앞 또는 현재 + 앞앞 계단을 밟는값중 큰 값을 가지도록 합니다.
이렇게 하면, 항상 최대값을 구하는 계단만 밟을것 같은데 논리에 오류가 있는지 궁금합니다.
질문 게시판의 반례들은 모두 정상적으로 나왔는데 틀렸습니다가 발생하니 어디가 문제인지 잘 모르겠습니다.