BOJ 2579번: 계단 오르기

문제

문제 바로가기> BOJ 2579번: 계단 오르기

2579번: 계단 오르기

풀이

주어진 조건을 만족하면서 다음 계단에 도착하는 방법은 다음과 같이 총 2가지이다.

 

1. 두 계단 전에서 현재 계단으로 : dp[i-2]+arr[i]

2. 한 계단 전에서 현재 계단으로 : dp[i-3]+arr[i-1]+arr[i]

 

따라서 위 점화식을 토대로 max 값을 찾아내면 된다!

 

#include<iostream>
#define MAX 301
using namespace std;

int N;
int arr[MAX], dp[MAX];

void input(){
    cin >> N;
    for(int i=1; i<=N; i++) cin >> arr[i];
}

void solution(){
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    for(int i=3; i<=N; i++) dp[i] = max(dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i]); // 두 계단 점프 or 한 계단 점프
    cout << dp[N]; // 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}