BOJ 2579: 계단 오르기

✔ 문제 링크

---

BOJ 2579: 계단 오르기

---

✔ 문제해결전략

• Dynamic Programming
• 1<=N<=300이므로 백트래킹(약 O(2^N)) 불가능

---

✔ 해결과정

✔ 테이블 정의

• dp[i] = i번째 계단까지 왔을 때 점수 합의 max
• 이렇게 정의하면 연속된 세 계단 모두 밟아서는 안 된다는 조건을 고려할 수 없다
• So, 매개변수를 추가해야 한다

---

✔ 새 테이블 정의

• dp[i][j] = 연속해서 j개의 계단 밟고 i번째 계단까지 왔을 때 점수 합의 max(i번째 계단은 밟은 거)
• j=1 or j=2

---

✔ 점화식

• dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i]
• dp[i][2] = dp[i-1][1] + score[i]

---

✔ Base Case

• dp[1][1] = score[1]
• dp[1][2] = 0
• dp[2][1] = score[2]
• dp[2][2] = score[1] + score[2]

---

✔ Code

#include <bits/stdc++.h>
using namespace std;

int score[301];
int dp[301][3]; // only 1, 2
// dp[k][1] = max(dp[k-2][1], dp[k-2][2]) + score[k]
// dp[k][2] = dp[k-1][1] + score[k]

int main() {
    	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	
	for(int i=1;i<=n;i++) {
		cin >> score[i];
	}
	
	// base case
	dp[1][1] = score[1];
    	dp[1][2] = 0;
    	dp[2][1] = score[2];
    	dp[2][2] = score[1] + score[2];
	
	
	for(int i=3;i<=n;i++) {
	    dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i];
	    dp[i][2] = dp[i-1][1] + score[i];
	}
	
	cout << max(dp[n][1], dp[n][2]);
}

---

✔ Check Point

처음에 최종 답을 dp[n][1] + dp[n][2]로 해서 틀렸다. 문제에서 묻고 있는 것은 총 점수의 최댓값이다. 따라서 n-1번째 계단이나 n-2번째 계단을 거쳐서 온 경우 중 더 큰 값을 구해야 한다. 무지성으로 풀지 말고 문제에서 구해야 하는 것이 무엇인지 제대로 체크하자.

ps) 요즘 초딩들은 이런 것도 푸나...??

---

✔ 참고문서

바킹독의 실전알고리즘 - 다이나믹 프로그래밍

바킹독님 감사합니다