백준 2579 : 계단 오르기 C++

www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

풀이

1. 우선 계단 3개 연속해서 못밟으니까 이전꺼랑 비교할때 이런 조건을 넣어야됨

 

max( 지금 직전+ 지금 3번째 전, 지금 2번째 전) 

 

2. 그렇기 때문에 당연히 dp 초기화도 0 1 2 이렇게 3개 해줘야된다.

 

 

#include<iostream>
#include<algorithm>
using namespace std;

int step[301];
int dp[301];

int main()
{
	int x;
	cin >> x;

	for (int i = 0; i < x; i++)
	{
		cin >> step[i];
	}

	dp[0] = step[0];
	dp[1] = step[0] + step[1];
	dp[2] = step[2] + max(step[1], step[0]);

	for (int i = 3; i < x; i++)
	{
		dp[i] = step[i] + max(step[i - 1] + dp[i - 3], dp[i - 2]);
	}

	cout << dp[x - 1];
	return 0;
}