백준 2579. 계단 오르기 (DP)

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

2579번: 계단 오르기

문제 풀이는 바킹독의 실전 알고리즘 0x10강 - 다이나믹 프로그래밍을 참고했다. 

 

1. 특징

1) DP

 

2. 구현 포인트(DP문제)

1) 테이블 정의하기

D[i][j] = 현재까지 j개의 계단을 연속해서 밟고 i번째 계단까지 올라섰을 때 점수 합의 최댓값, 단 i번째 계단은 반드시 밟아야 함

 

2) 점화식 찾기

D[k][1] = max(D[k-2][1] + D[k-2][2]) + S[k]

D[k][2] = D[k-1][1] + S[k]

 

3) 초기값 정하기

D[1][1] = S[1], D[1][2] = 0

D[2][1] = S[2], D[2][2] = S[1] + S[2]

 

3. 코드

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <limits.h>
#include <algorithm>
using namespace std;

int n;
int arr[304];
int ans[304][3];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    
    for(int i = 1; i <= n; i++)
    {
        cin >> arr[i];
    }

    ans[1][1] = arr[1]; 
    ans[1][2] = 0;
    ans[2][1] = arr[2]; //두번째 전에서 온경우
    ans[2][2] = arr[1] + arr[2]; //첫번째 전에서 온경우
    for(int i = 3; i <= n; i++)
    {
        ans[i][1] = max(ans[i-2][1], ans[i-2][2]) + arr[i];
        ans[i][2] = ans[i-1][1] + arr[i];
    }

    cout << max(ans[n][1], ans[n][2]);
    

}