[PS] BOJ_2579

최윤하·2022년 3월 26일
0

Problem Solving

목록 보기
6/12
post-thumbnail

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();

💥 발전하자

  • 에러 및 해결
  1. 처음에는 점화식을 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'이 되는데, 이는 최댓값이 아니다.
    이렇듯 위의 점화식은 언뜻 보면 맞는 것 처럼 보이지만 틀린 점화식임을 알 수 있다.

📌 참고하자

나의 코드(Github)

0개의 댓글