[C/C++] 백준 2579번 - 계단 오르기

✏️ 문제 링크

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

 

 

✏️ 문제 설명

 

 

✏️ 문제 풀이

가장 먼저 dp배열을 만들어줬는데 dp[i]는 i번째 계단을 밟을 때 얻을 수 있는 최대의 점수로 지정하였습니다. 그리고 나서 dp[1], dp[2], dp[3]값을 각각 지정해 주었습니다. dp[1] = stair[1]이고 dp[2] = stair[1] + stair[2]이고 dp[3]의 경우를 잘 생각해주어야 합니다. 왜냐면 3번째 계단은 1번째 계단 + 3번째 계단 이거나 2번째 계단 + 3번째 계단인 경우 중 하나이기 때문에 다짜고짜 반복문을 돌리게 되면 dp[3]에 다른 값이 지정되지 않을 수도 있습니다. 그런다음 반복문을 돌리면서 dp[i]의 값을 갱신해 주었습니다.

dp[i] = max(dp[i-2], dp[i-3] + stair[i-1]) + stair[i];  

이렇게 설정한 이유는 문제에서 제시한 1, 2번 조건을 지키기 위해서입니다. dp[i-2]를 밟고 stair[i]를 밟으면 한 번에 두계단을 점프하므로 문제가 없고  dp[i-3] + stair[i-1]를 밟고 stair[i]를 밟게 되면 연속해서 두 계단을 밟더라도 세 계단을 연속해서밟는 경우는 발생하지 않습니다.

 

 

✏️ 문제 코드

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
   int n, dp[100000]={0}, stair[100000]={0};
   cin>>n;
   for(int i=1;i<=n;i++)
   {
       cin>>stair[i];
   }
    dp[1]=stair[1];
    dp[2]=stiar[1]+stair[2];
    dp[3]=stair[3]+max(stair[1],stair[2]);
    for(int i=4;i<=n;i++)
    {
        dp[i]=max(dp[i-2],dp[i-3]+stair[i-1])+stair[i];
    }
    cout<<dp[n];
    return 0;
}