[Baekjoon] 2579번: 계단 오르기

🥅 문제

https://www.acmicpc.net/problem/2579

 

🔍 설계

시작점은 계단에 포함되지 않는다.

한 계단에서는 다음 계단이나 다다음 계단으로 이동할 수 있다.

마지막 계단은 무조건 밟아야 한다.

 

재귀로 구현한다면, 계단의 개수가 300개이므로, O(2^300)이므로 시간 초과가 발생할 것이다.

 

어떤 계단까지의 점수 중 최댓값은 전 계단까지의 점수+어떤 계단의 점수와 전전 계단까지의 점수+어떤 계단의 점수를 비교하여 구할 수 있다. 예를 들어, 5번째 계단까지의 총 점수를 구하는데, 3번째와 4번째 계단의 점수가 활용된다는 것이다. 즉, 다이나믹 프로그래밍을 이용하여 구할 수 있다. 

 

어떤 계단까지의 점수를 단순히 하나로 저장하면 안된다. 다음 계단에서 점수를 계산할 때, 어떤 계단까지의 점수가 이미 2번 연속되었다면, 다음 계단에서 3번 연속되어 그 점수를 이용할 수 없기 때문이다. 따라서 연속 횟수에 따라 분리하여 저장해야 한다.

dp[i][1], dp[i][2]는 각각 i번째 계단까지 연속 횟수가 1, 2라는 의미이고, dp[i][0]은 둘 중 최댓값을 저장하였다.

 

예외적으로, 첫 번째 계단은 시작점으로부터 도달할 수 밖에 없으므로, 연속 횟수가 1이고, 계단이 1개인 경우도 있으므로 최댓값을 갱신해주어야 한다.

 

👊 풀이

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
using namespace std;	
int n;
vector<int> stage(301);
vector<vector<int>> dp(301, vector<int>(3));

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	
	cin >> n;
	for (int i=1; i<=n; i++){
		cin >> stage[i];
	}

	dp[1][1] = stage[1];
	dp[1][0] = stage[1];
	for (int i=2; i<=n; i++){
		dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + stage[i];
		dp[i][2] = dp[i-1][1] + stage[i];
		dp[i][0] = max(dp[i][1], dp[i][2]);
	}

	cout << dp[n][0] << "\n";

	return 0;
}

 

📝 메모

첫 번째 계단의 최댓값도 갱신해주어야 한다.