[백준] 2579 계단 오르기 DP

문제 :

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

2579번: 계단 오르기

 

분석 :

 

계단이 있을 시 계단을 오르는데 규칙이 있다 --> 점화식이군

---

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

---

 

stairArr [i] = i번째 계단의 값

d [i] = i번째 계단까지 밟았을때 총 계단의 최대 값 

 

 

1번째 계단을 밟았을때 최대 값은 계단을 밟아야 한다 --> d[0] = stairArr[0]

 

2번째 계단을 밟았을때 최대 값은 두 계단을 모두 밟아야 한다 -> d[1] = stairArr[0] + stairArr[1]

 

3번째 계단을 밟았을때 최대 값은 3번째 계단을 밟고 1, 2 중 하나의 계단만을 밟아야 한다 -> max(stairArr[0], stairArr[1]) + stairArr[2]

 

따라서 점화식은 

마지막 계단을 밟았을때 전전 계단까지의 최대 값과 // 마지막 계단을 밟았을 때 전전전 계단까지의 최대 값 + 전전 계단의 값으로 정리할 수 있다.

따라서 !!

 

        d[i] = max(d[i - 3] + stairArr[i - 1] + stairArr[i], d[i - 2] + stairArr[i])

 

가 된다.

 

 

 

c++ 풀이 :

//
//  2579_stairUp.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/06/13.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;
int Tcase;
int stairArr[301] = {0, };
int d[10001] = {0, };

int find_best_DP(){
    int answer = 0;
    d[0] = stairArr[0];
    d[1] = stairArr[0] + stairArr[1];
    d[2] = max(stairArr[0], stairArr[1]) + stairArr[2];
    
    for(int i = 3; i < Tcase; i++){
        //전전전 계단까지 최대 값 + 전 계단 + 마지막 계단, 전전 계단까지의 최대 값 + 마지막 계단
        d[i] = max(d[i - 3] + stairArr[i - 1] + stairArr[i], d[i - 2] + stairArr[i]);
    }
    answer = d[Tcase - 1];
    return answer;
}

int main(){
    cin >> Tcase;
    for(int i = 0; i < Tcase; i++){
        cin >> stairArr[i];
    }
    
    cout << find_best_DP() << '\n';
    return 0;
}