[Algorithm] Baekjoon 2579번 : 계단 오르기

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

2579번: 계단 오르기

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int input = 0;
    vector<int> v;
    int dp[301] = { 0 };
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> input;
        v.push_back(input);
    }
 
    dp[0] = v[0];
    dp[1] = v[0] + v[1];
    dp[2] = max(v[0] + v[2], v[1] + v[2]);
 
    for (int i = 3; i < v.size(); i++)
    {
        dp[i] = max(v[i] + v[i - 1] + dp[i - 3], v[i] + dp[i - 2]);
        
    }
 
    cout << dp[n - 1] << endl;
}

 

오랜만에 풀었던 DP문제. 내 약점이 여실히 드러났던 시간이였다.

 

그래도 처음 접했을때보다 뭔가 감이라해야하나? 그런건 좀 생긴거 같은데 깔끔하게 정답으로까지 도출해내진 못했다.

 

이 문제에서의 조건은, 연속으로 세번째계단을 밟을 수 없다는 것이다. 

 

3번째 계단을 밟으려면  맨처음위치 -> 2 -> 3 or 맨처음위치 -> 1 -> 3   .. 이렇게 밟아야 한다.

 

이걸 생각하면서 DP[i] 값을 어떻게 구해야하는지 생각해야 한다.

 

위의 조건을 기준으로 생각하면, 특정 i번째 계단을 정상적으로 밟으려면

 

i-3 -> i-1 -> i 이렇게 밟던가,

 

i-2 -> i 이렇게 밟아야 한다.

 

여기서 빨간색 부분이 dp배열이다.

 

어떻게 저렇게 나오는가?를 쉽게 설명하지는 못하겠는데, 순수하게 i번째 계단의 최대값을 구해야한다는것만 알도록 하자.

 

저 빨간색부분인 dp[i-3]과 dp[i-2]가 왜 딱 저부분만 dp일까?

 

저 i-3번째와 i-2번째 이전에는 어떤 순서로 계단을 밟든, 상관없기 때문이다.

 

즉 저 부분은 문제의 조건에 걸리지 않는, 문제의 조건을 시작하는 단계이기 때문이다.

 

첫번째인 빨간색 i-3부분 이전에, 그 i-3밟기 이전에 i-4를 밟았든.. i-5를 밟았든 아무 상관없다.

 

빨간색 i-2부분도 마찬가지. 이전에 i-3을 밟았든, i-4를 밟았든 조건에 전혀 위배되지 않는다.

 

일단 이렇게 정리하긴 했는데.. 다른 유형의 문제도 마찬가지겠지만, DP문제는 진짜 많이 풀어봐야 할 것 같다.

 

어쨌든 이문제는 조건을 쉽게 찾아낸다면 금방 풀 수 있는 문제들이 많아서.. 이번년도 회사들 코테에서도 많은 비중은 아니지만 나오긴 했다.