[백준] 2579 - 계단오르기 (C++)

문제 출처:

www.acmicpc.net/problem/2579

2579번: 계단 오르기

문제 풀이:

• 이 문제는 3가지 조건을 지켜야한다.

1. 한번에 2개 혹은 1개 씩 오른다.
2. 연속으로 3개의 계단을 밞으면 안됨(다만 시작점은 계단에 포함되지않는다)
3. 마지막 계단은 반드시 밟아야한다.

• 여기서 3번 조건을 이용하는게 핵심적이라고 생각한다.
• 필자는 처음부터 밟는다고 생각한 뒤 풀었는데 그런경우 마지막 계단을 밟을 수 있는지 체크하는 부분이 굉장히 복잡하게 느껴졌다.
• 때문에 마지막 계단을 밟았다고 생각하고 진행을 하니 훨씬 풀기가 수월했다.

.....  n-3    n-2    n-1    n (원래는 n-1이 맞지만 보기 편하게 하기 위해서 n으로 쓰겟다)

                  dp       X     O
         dp      X        O     O

 

• dp[i] = i번째 계단에서 얻을 수 있는 최대합 
• 위와 같은 경우를 수식화하면
  dp[i] = max(dp[i-3]+s[i-1]+s[i],dp[i-2]+s[i])
  가 된다.
• 이런 경우 n=1, n=2 인 경우에 index 오류가 날 수 있으니 따로 처리해주었다.

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

int dp[301];
int s[301];

void init_var()
{
    for(int i =0;i<302;i++)
    {
        dp[i]=0;
        s[i]=0;
    }
}

int main()
{
    init_var();
    int n=0;
    int tmp=0;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin >> tmp;
        s[i]=tmp;
    }

    if(n==1)
    {
        cout << s[0];
        return 0;
    }
    else if(n==2)
    {
        dp[0]=s[0];
        dp[1]=s[0]+s[1];
        cout << dp[1];
        return 0;
    }
    else{
        dp[0]=s[0];
        dp[1]=s[0]+s[1];
        dp[2]=max(s[0]+s[2],s[1]+s[2]);

        for(int i=3;i<n;i++)
        {
            dp[i]=max(dp[i-3]+s[i-1]+s[i],dp[i-2]+s[i]);
        }
        cout << dp[n-1];
        return 0;
    }
}