[백준(BOJ)] 2579번: 계단 오르기 (Dynamic Programming , C++)

📝 문제풀이 과정

---

BOJ:2156번(포도주 시식) 문제를 참고해서 점화식을 생각했다.

 

• 점화식에서 DP[i-3]이 사용되므로, 0~2번째에 대한 초기값이 필요하다.
  • DP[0] = A[0]
  • DP[1] = max(A[1], A[1] + A[0])
  • DP[2] = max(A[1] + A[2], A[0] + A[2])
• 3번째부터는 점화식을 사용한다.
  
  • i-1번째를 포함하는 경우 DP[i] = DP[i-3] + DP[i-1] + DP[i]
  • i-1번째를 포함하지 않는 경우 DP[i] = DP[i-2] + DP[i]
  • 이 두 경우에 대한 max 값을 DP[i]로 가져간다.

 

A[0] 10
A[1] 20
A[2] 15
A[3] 25
A[4] 10
A[5] 20

위와 같이 테스트케이스가 있을 때, DP[3]부터는 A[0] + A[1] + A[3]을 하는 경우 (DP[i-2] + A[i])와 A[0] + A[2] + A[3] (DP[i-3] + A[i-1] + A[i])가 있고, 두 경우에서 더 큰 55를 DP[3]에 저장한다.

 

DP[0]: 10
DP[1]: 30
DP[2]: 35
DP[3]: 55
DP[4]: 65
DP[5]: 75

DP는 위와 같으며, 마지막은 항상 포함되므로 DP[n-1]을 출력한다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
    int n;
    scanf("%d", &n);
    int A[n] = {};
    int DP[n] = {};

    for(int i=0; i<n; i++) scanf("%d", &A[i]);

    DP[0] = A[0];
    DP[1] = max(A[1], A[0] + A[1]);
    DP[2] = max(A[1] + A[2], A[0] + A[2]);

    for(int i=3; i<n; i++){
        DP[i] = max(DP[i-2] + A[i], DP[i-3] + A[i-1] + A[i]);
    }

    printf("%d", DP[n-1]); // 마지막은 항상 포함이므로
}

 

 

👏 결과

---