[알고리즘][BOJ]2579_계단 오르기
💡 생각하자
[Dynamic Programming(동적 계획법)의 개발절차]
1. 재귀 관계식(recursive property) 세우기
2. 상향식 방법(bottom-up)으로 답 구하기
문제의 조건에 의해 마지막 계단(n번째 계단)은 무조건 밟아야 하므로, 경우의 수는 2가지가 존재한다.
1) n-2번째 계단 -> n번째 계단
2) n-1번째 계단 -> n번째 계단
단, 이 경우에는 연속된 3개의 계단을 밟을 수 없다는 조건에 의해 무조건 'n-3 -> n-1 -> n' 의 순서를 가지게 된다.
재귀 관계식
stairs[n] = n번째 계단의 점수
S[n] : n번째 계단까지 오를 때 얻을 수 있는 점수의 최댓값
S[n] = maximum(S[n-2] + stairs[n], S[n-3] + stairs[n-1] + stairs[n]) (n >= 3)
💻 구현하자
- 점수의 최댓값을 계산하는 함수
int calMax() {
for (int i = 3;i <= n;i++) {
S[i] = maximum(S[i - 2] + stairs[i], S[i - 3] + stairs[i - 1] + stairs[i]);
}
return S[n];
}
- 초기 호출문
S[0] = 0;
S[1] = stairs[1];
S[2] = stairs[1] + stairs[2];
int res = calMax();
💥 발전하자
- 에러 및 해결
- 처음에는 점화식을 S[n] = maximum(S[n-2] + stairs[n], S[n-1] + stairs[n])으로 세우고, 연속된 3개의 계단을 밟는 경우를 따로 체크해주었다.
이 경우, stairs = {10, 3, 2, 1, 100, 100}과 같은 반례가 존재하였다.
예를 들어, S[6] = maximum(S[5] + 100, S[4] + 100) = maximum(224, 114)가 된다.
하지만 S[5]라는 값은 그 이전에 '1->2->4->5'의 순서에 의해 결정 되었으므로, S[5]를 선택하게 되면 '4->5->6'이 되어 연속된 3개의 계단을 밟게 된다.
그러므로 S[4]를 선택하여 '1->2->4->6'이 되는데, 이는 최댓값이 아니다.
이렇듯 위의 점화식은 언뜻 보면 맞는 것 처럼 보이지만 틀린 점화식임을 알 수 있다.
📌 참고하자
Author And Source
이 문제에 관하여([알고리즘][BOJ]2579_계단 오르기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@choiyhking/알고리즘BOJ2579계단-오르기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)