[백준] 알고리즘 2579번 - 계단 오르기 문제

#include<bits/stdc++.h>
using namespace std;
int dp[301];
int arr[301];
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	dp[1] = arr[1];
	dp[2] = max(arr[1] + arr[2], arr[2]);
	dp[3] = max(arr[1] + arr[3], arr[2] + arr[3]);
	for (int i = 4; i <= n; i++) {
		dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);
	}
	cout << dp[n];
}

• dp1=첫번째 계단 올랐을 경우
• dp2=첫번째 계단 오른경우+두번째 계단 오른경우 와 두번째 계단을 바로 가는 경우를 비교
• dp3=첫번째 계단+셋번째 계단과, 두번째 계단과 세번째 계단을 올랐을 때 경우를 비교

dp4 = 4번째 계단을 오를 때의 최대값이 저장되어야 한다.

 

dp4의 경우의 수

dp1,2,3 에는 경우의 수들의 최대값이 들어 있기때문에 첫번째 칸에서 3,4 가는경우와 2번째에서 바로 4번째 가는 경우를 비교해주면, 연속으로 3번을 피해 모든 경우를 비교할 수 있다.