[BOJ] 2579 계단 오르기

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

2579번: 계단 오르기

---------------------------------------------------핵심 알고리즘--------------------------------------------

 

dp

 

---------------------------------------------------풀이----------------------------------------------------

 

dp[계단 순서][계단 선택 유/무] = 그 계단까지 갈 때 최댓값

위와 같은 배열을 선언해 사용하였다.

k번째 계단이라고 할 때,

k번째 계단을 선택하지 않을 때의 최댓값은 k-1번째 계단을 선택할 경우와 같다.

따라서 dp[k][0] = dp[k-1][1]이다.

k번째 계단을 선택할 경우, 세 개가 연속되지 않도록 하는 것이 핵심이다.

즉, k-2번째 계단을 선택하지 않고 k-1번째 계단은 선택하거나, k-1번째 계단을 선택하지 않는 방법이 있다.

이 중 큰 값을 취하면 된다.

따라서 dp[k][1] = max(dp[k-2][0] + scores[k-1], dp[k-1][0]) + scores[k]이다.

 

-2번째까지 봐야 하므로

0번째와 1번째 계단에 대해서는 미리 최댓값을 저장해두었다.

#define FASTIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stack>
#include <limits.h>

using namespace std;

int scores[305] = {0, };

// dp[계단 순서][계단 선택 유무] = 그 계단까지 갈 때 최댓값
int dp[305][2] = {0, };

// 계단 오르기 규칙
// 1. 한 번에 하나 또는 두 개를 오를 수 있다.
// 2. 연속된 세 개를 모두 밟으면 안 된다. 시작점은 계단으로 안 침
// 3. 마지막 계단은 반드시 밟아야함.
int main(void){
    FASTIO;
    // 계단의 개수
    int N;
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> scores[i];
    }

    // 현재 계단 선택 x = dp[k][0] = dp[k-1][1] = 이전 계단 선택할 경우의 최댓값
    // 현재 계단 선택 o = dp[k][1] = max(두 개 전 선택x+이전꺼선택, 이전꺼 선택x) + 현재 선택
    //                         = max(dp[k-2][0]+scores[k-1], dp[k-1][0]) + scores[k]
    dp[0][0] = 0; dp[0][1] = scores[0];
    dp[1][0] = dp[0][1]; dp[1][1] = dp[0][1] + scores[1];
    for(int i = 2; i < N; i++){
        dp[i][0] = dp[i-1][1];
        dp[i][1] = max(dp[i-2][0]+scores[i-1], dp[i-1][0]) + scores[i];
    }

    // 마지막 계단을 밟았을 때의 최대 점수
    cout << dp[N-1][1] << "\n";
    return 0;
}

 

---------------------------------------------------후기----------------------------------------------------

 

dp 문제인데 실버3 수준인걸 보니 대표적인 dp 유형인가보다..

보자마자 dp인것 같긴 했는데 어떻게 풀지 생각하는데 조금 걸렸다. 세 개를 연속되지 않게 하려고 하는 부분에서 조금 헤맸다.

그래도 30분만에 다 푼걸 보니 쉽긴 한가보다!