[BOJ알고리즘, C++]#2579_계단 오르기, DP

 

#1. 문제

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

 

---

 

#2. 풀이

 

1. DP

[알고리즘]#5_동적 계획법

DP는 입력 크기에 따라 중복되는 하위 문제들을 재귀적으로 해결하고, 결과 값을 기억함으로써 중복 계산을 방지하는 최적화 기법입니다. 대표적으로, 트리 자료구조에서 주로 활용되며 DFS 구현과 함께 활용되기도 합니다.

2. 패턴을 파악하고, 점화식을 먼저 세우자

점화식:
            dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i]
            dp[i][2] = dp[i-1][1] + score[i];

1. 먼저, 각 계단에 대하여 두 가지 경우의 결과 값을 저장해야 합니다. 하나는 해당 계단을 밟았을 경우, 다른 하나는 해당 계단을 밟지 않았을 경우입니다. 따라서, 2차원 배열 형식의 DP [MAX][MAX]가 필요합니다.

 

---

 

#3. 코드

/*
    @문제: 계단 오르기 게임을 통해 얻을 수 있는 최대 값
    @설명
        1. 한 칸 혹은 두 칸을 이동할 수 있다.
        2. 연속한 세 계단을 모두 밟을 수 없다.
        3. 마지막 계단은 무조건 밟아야 한다.
        4. 점화식:
            dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i]
            dp[i][2] = dp[i-1][1] + score[i];
*/

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

#define MAX 301

vector<int> score;
int dp[MAX][2]; // 1: i-1번 계단을 밟지 않았을 경우, 2: i-1번 계단을 밟았을 경우
int N;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;

    score.resize(N+1);
    for(int i=1; i<=N; ++i)
    {
        cin >> score[i];
    }

    dp[1][1] = score[1];
    dp[1][2] = score[1];
    for(int i=2; i<=N; ++i)
    {
        dp[i][1] = max(dp[i-2][1], dp[i-2][2]) + score[i];
        dp[i][2] = dp[i-1][1] + score[i];
    }

    cout << max(dp[N][1], dp[N][2]);

    return 0;
}

 

---