[백준 2579번 C/C++] 계단 오르기

 

 

목차

 

 

---

 

 

[백준 2579번 C/C++] 계단 오르기

 

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

2579번: 계단 오르기

---

 

해결전략

 

Dynamic Programming (DP)

 

도착지점이 i번째 계단이라면 올라가는 방법은

• ( i - 3 )번째 계단에서 2칸 올라간 후 ( i - 1)번째 계단에서 1칸 올라가거나
• ( i - 2 )번째 계단에서 2칸으로 올라가거나

둘 중 하나이다.

 

---

 

코드

 

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

int n;
int stair[301];
int sum[301];

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	cin >> n;

	for(int i=1; i<=n; i++){
		cin >> stair[i];
	}

	sum[1] = stair[1];
	sum[2] = stair[1] + stair[2];
	sum[3] = max(stair[1], stair[2]) + stair[3];
	sum[4] = max(stair[1] + max(stair[2], stair[3]), stair[2]) + stair[4];

	for(int i=5; i<=n; i++)
	{
		sum[i] = max(sum[i-3] + stair[i-1], sum[i-2]) + stair[i];
	}

	cout << sum[n];

	return 0;
}