[백준(BOJ)] 2579번 : 계단 오르기 - C++[CPP]

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

2579번: 계단 오르기

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 다이나믹 프로그래밍

 

---

 

⊙ 문제 접근 과정

 

DP 문제다. 규칙성을 찾고 점화식을 세워 풀면 된다.

---

 

⊙ 문제 풀이

 

#include <iostream>

using namespace std;
#define MAX 301

int N;
int stairs[MAX];
int dp[MAX];

int main() {
    cin >> N;

    for(auto i=0;i<N;i++) 
        cin >> stairs[i];
    
    dp[0] = stairs[0];
    dp[1] = max(stairs[1],stairs[0]+stairs[1]);
    dp[2] = max(stairs[0] + stairs[2],stairs[1]+stairs[2]);

    for(auto i=3;i<N; i++) 
        dp[i] = max(stairs[i] + dp[i-2], stairs[i]+stairs[i-1] +dp[i-3]);

    cout << dp[N-1];
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!