[백준 2579] 계단 오르기

0. 제목

• 백준 2579 계단 오르기
• BOJ 2579 계단 오르기
• C++ 2579 계단 오르기

---

1. 문제

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

---

2. 풀이

• DP 방식을 이용하였다.
• [백준 2156] 포도주 시식 문제와 비슷하다.
• 먼저 초기값인 dp[1], dp[2], dp[3] 을 먼저 설정해준다.
• 문제에서 계단을 오를때 항상 마지막 계단을 밟아야 한다고 나와있다. 마지막 계단을 i번째 계단이라고 놓으면 i-1 번째 계단과 i-2 번째 계단을 밟는 경우를 생각해봐야 한다.
• i-1 번째 계단을 밟을 경우 3개 연속으로 밟으면 안되므로 i-2번째는 밟을 수 없다. 따라서 dp[i-3] + arr[i-1] + arr[i] 가 된다
• i-2 번째 계단을 밟을 경우는 그대로 dp[i-2] + arr[i] 가 된다.
• 따라서, 위 두개의 값 중에 큰 값이 정답이 된다.

---

3. 코드

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    int N;
    int arr[301];
    int dp[301];
    
    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> arr[i];
    
    dp[1] = arr[1];
    dp[2] = arr[1] + arr[2];
    dp[3] = max(arr[1],arr[2])+arr[3];
    for(int i = 4; i <= N; i++)
        dp[i] = max(dp[i-3] + arr[i-1], dp[i-2]) + arr[i];
    
    cout << dp[N] << '\n';
    
    return 0;
}