[백준][C++] 2579 계단 올라가기

2579 계단 올라가기

2579번: 계단 오르기

문제 풀이

 

정말 무지무지 어렵게 느껴졌던 문제...

결국 혼자서 풀지 못하고 다른 사람의 코드를 보고 이해했다.

 

1. 첫번째 계단을 꼭 밟아야 한다고 생각한 것
2. 계단 세 칸 이상을 가면 안 된다는 조건을 고려하지 않은 것

 

처음엔 정렬을 썼다. 큰 수들의 계단을 먼저 고르고 세 번 연속 고르지 못하도록 bool형 배열을 써서 체크해주었다.

#include<bits/stdc++.h>
using namespace std;

vector<pair<int, int>> stairs;
int scores[300];
bool check[300] = { false, };
bool Check(int i, bool check[300]);

int main()
{
    int len, answer = 0;
    cin >> len;
    stairs.resize(len);

    for (int i = 0; i < len; i++)
    {
        cin >> stairs[i].second;
        stairs[i].first = i;
        scores[i] = stairs[i].second;
    }

    // staits 오름차순 정렬
    sort(stairs.begin(), stairs.end());

    // 첫 계단과  마지막 계단 건너기
    // 여기서 잘못했다... 첫 계단은 꼭 건널 필요가 없다...
    check[0] = check[len - 1] = true;

    // 점수가 큰 계단부터 건너준다
    for (int i = 1; i < stairs.size() - 1; i++)
    {
        int j = stairs[i].first;

        // 3번 연속 있는지 체크
        if (Check(j, check))
        {
            check[j] = true;
            answer += stairs[i].second;
        }
    }

    cout << answer + scores[0] + scores[len - 1] << endl;
}

// 3번 연속 있는지 체크해주는 
bool Check(int index, bool check[300])
{
    check[index] = true;
    int temp = 0, imax = 0;

    for (int i = -2; i <= 2; i++)
    {
        (check[index + i]) ? temp++ : temp = 0;
        imax = max(temp, imax);
    }

    check[index] = false;

    return (imax < 3);
}

코드는 나름 짰으나... 조건을 지키는 않은 답안에 정답이 있을리는 없었다.

틀린 이유를 분석하다가, 조건을 지키지 않은 것을 보고 얼른 새로운 로직을 생각해내려고 했다.

 

생각해내려고 했는데...

도무지 생각이 나지가 않았다.

정말 야자 시간을 모두 써서 이런 저런 생각도 해보고... 테스트케이스를 만들어 그럴듯한 코드도 짜봤지만... 역시 모두 실패였다.

 

그래서 결국 다른 사람의 코드를 보고, 이해하고 분석해서 내 것으로 만들기로 했다. ㅠㅠ

[ 백준 2579 ] 계단오르기 (C++) :: 얍문's Coding World..

이 분의 DP 코드를 참고했다.

 

점화식을 분석해보자면...

DP[1] = Stairs[1]
DP[2] = DP[1] + Stairs[2]
DP[3] = max(Stairs[1], Stairs[2]) + Stairs[3];

// 2 => 1>2
// 3 => 1>3 or 2>3

그럼 4, 5, 6... N은?

DP[N] = max(DP[N-2], Stairs[N-1] + DP[N-3]) + Stairs[N]

 

두 칸 전에 누적된 값들과 세 칸 전에 누적된 값 + 한 칸 전 계단 값을 비교하는 점화식이었다.

 

어렵지 않은 문제였는데...... 이상한 데에서 자꾸 뭘 추가하고 삽질을 하느라 시간이 오래 걸렸다...

분석한 걸 그림으로 정리해봤다.

그림으로 정리하니 더 이해가 잘 된다.

나중에 다시 한 번 더 풀어볼 문제 같다.