개발 블로그

문제 링크 : www.acmicpc.net/problem/2579

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

접근 방법

1) 현재 계단을 밟지 않고 건너 뛰는 경우

2) 현재 계단을 밟는 경우

이렇게 두가지로 나눌 수 있다.

1)번의 경우에 계단의 합의 최대값은 직전의 최대값과 같다. 이 경우엔 현재 계단을 선택하지 않으므로 3개 연속 유무를 신경쓰지 않아도 된다.

2)번의 경우에 계단의 합의 최대값은, 현재 계단을 포함해서 3개 이상 연속되는 경우를 제외해야 한다. 그러므로 직전 계단에서 2개 이상 연속한 경우를 제외하고, 나머지 후보들을 비교해서 최대합을 찾으면 된다.

문제의 입력 예시를 보자.

6개의 계단 값은 10 20 15 25 10 20 이다.

벡터 배열안에 <합, 연속해서 밟은 계단 수> 를 저장했고, 저장할 때마다 합을 비교해서 마지막에 최대합을 dp[]에 저장했다.

벡터 배열 값을 보면 아래와 같다. 

10    vecArr[0] : <0,0>/  <10,1>  -> dp[0] = 10

20   vecArr[1] : <10,0> / <0+20, 1> <10+20, 2>  ->dp[1] = 30

15    vecArr[2] : <30,0> / <10+15, 1> <0+20+15,2>  ->dp[2] =  35

25   vecArr[3] : <35, 0> / <30+25, 1> <10+15+25, 2>  -> dp[3] = 55

10   vecArr[4] : <55,0> / <35+10, 1> <30+25+10, 2>  -> dp[4] = 65

20   vecArr[5] : <65,0> / <55+20, 1> <35+10+20, 2>  -> dp[5] = 75

//
//  DP_BOJ2579_계단오르기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;

int stair[300] = {0};
int dp[300] = {0};
vector<pair<int,int>> vecArr[300];

int main(){
    
    int N; cin >> N;
    for(int i = 0; i<N; i++){
        cin >> stair[i];
    }
    
    //dp[0], dp[1] 초기화
    vecArr[0].push_back(make_pair(0,0));            //-1
    vecArr[0].push_back(make_pair(stair[0],1));     //0
    
    dp[0] = stair[0];
    
    vecArr[1].push_back(make_pair(dp[0], 0));               //0 x
    vecArr[1].push_back(make_pair(stair[1], 1));            //x 1
    vecArr[1].push_back(make_pair(stair[0] + stair[1], 2)); //0 1
    
    int maxi=0;
    for(int i = 0; i<3; i++){
        if(maxi<vecArr[1][i].first) maxi = vecArr[1][i].first;
    } dp[1] = maxi;
    
    
    
    for(int i = 2; i<=N-1; i++){
        
        //case 1 : 현재 계단 안 밟는 경우
        if(i!=N-1){     //문제의 조건에서 마지막 계단은 무조건 밟는다고 했음
            vecArr[i].push_back(make_pair(dp[i-1], 0));     //직전 계단까지 왔을 때 최대값
        }
        
        //case 2 : 현재 계단 밟는 경우
        int maxi = 0;
        for(int j = 0; j<vecArr[i-1].size(); j++){
            int conti = vecArr[i-1][j].second;
            if(conti==2) continue;                  //직전 계단까지 2개 연속해서 밟은 경우, 3개 연속 못 밟음
            
            int sum = stair[i] + vecArr[i-1][j].first;
            if(maxi < sum) maxi = sum;
            vecArr[i].push_back(make_pair(sum,conti+1));    //현재 계단 밟았으므로 연속해서 밟은 계단 수 1증가해서 저장
 
        }
        dp[i] = maxi;
        
    }
    cout << dp[N-1];
    
    return 0;
}