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

 

#include <stdio.h>

#include <iostream>

using namespace std;

int max_score(int a, int b)

{

    return a > b ? a : b;

}

int main(void){

    

    int stair_num;                  // 계단수 변수

    int stair_score[301] = {};      // 계단수 300

    int store[301] = {};            // 계단 저장 배열 변수(dp)

    scanf("%d", &stair_num);        // 계단수 입력

    

    // 계단 점수 입력

    for (int i = 1; i <= stair_num; i++){

        scanf("%d", &stair_score[i]);

    }

    store[1] = stair_score[1];

 

    //계단을 한번 밟았다고 생각하였을때 값 dp값 저장

    if(stair_num >= 2){

        store[2] = store[1]+stair_score[2];

    }

    

    for(int i=3; i<=stair_num; i++){

        // 계단이 한번연속인 경우 - N계단 N-1번째 계단 생각 X , N-2번째 계단의 총점 생각

        // 계단이 두번연속인 경우 - N계단 2번 연속일 경우 N-1계단은 밟아야함 , N-2밟아버리면 규칙어긋나버림(최대가 될수없음) , N-3 계단까지 얻은 점수 합

        

        store[i] = max_score(store[i-2]+stair_score[i],store[i-3]+stair_score[i-1]+stair_score[i]);

    }

    

    printf("%d\n", store[stair_num]);

}