Coding Test - cpp/DP
[백준 2579: 계단 오르기] - C++
에드윈H
2021. 1. 19. 12:46
2579번: 계단 오르기
계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점
www.acmicpc.net
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
#define MAX 301
int DP[MAX];
int stair[MAX];
int main()
{
int n = 0;;
cin >> n;
for (int i = 0; i < n; i++) cin >> stair[i];
DP[0] = stair[0];
DP[1] = max(stair[1], stair[0] + stair[1]);
DP[2] = max(stair[0] + stair[2], stair[1] + stair[2]);
for (int i = 3; i < n; i++)
{
DP[i] = max(stair[i] + DP[i - 2],
stair[i] + stair[i - 1] + DP[i - 3]);
}
//result
cout << DP[n - 1];
return 0;
}//end of main