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

문제

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

2579번: 계단 오르기

코드

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

using namespace std;
/*
계단 오르기(2579)
계단 아래 시작점부터 계단 꼭대기에 위치한 도착지까지 가야함
각각의 계단에는 일정한 점수가 쓰여 있음. 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 됨
계단을 오르는 규칙
1. 계단은 한번에 1 혹은 2 계단 씩 오를 수 있음 
2. 연속된 세개의 계단을 모두 밟아소는 안됨
3. 마지막 도착 계단은 반드시 밟아야 함
각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하자
- 
이전의 최대 -> 다음의 최대 => dp문제!!
*/

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // 속도 더 빠르게 해줌

    int num;
    cin >> num;

    vector<int> stair(num + 1, 0);
    vector<int> score(num + 1, 0);

    for (int i = 1; i <= num; i++) { // 계단 입력받기
        cin >> stair[i];
    }

    score[1] = stair[1];
    score[2] = stair[1] + stair[2];

    for (int i = 3; i <= num; i++) {
        // 현재 계단을 밟았을 때의 경우를 고려
        score[i] = max(score[i - 2], score[i - 3] + stair[i - 1]) + stair[i];
    }

    cout << score[num];

    return 0;
}

풀이

이전의 최대 -> 다음의 최대 => dp문제!!

첫번째 계단을 밟을 때와 두번째 계단 밟는 경우는 미리 지정해두고 세번째 계단 밟을 때부터 경우의 수를 두개씩 비교해주어 큰 것 선택해준다.  ex) 0-1-3, 0-2-3 고려

오답 + 이유

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

using namespace std;

/* 틀린 코드
두 번째 계단을 밟을 때, 세 번째 계단까지 이어서 밟을 수 있는 경우를 고려하지 않음. 
: 0-2-3의 경우 고려 못했음. 0-1-2-4, 0-1-3만 고려했었음
세 번째 계단까지 밟을 수 있는 경우를 확인하고 수정한 뒤, 두 계단을 연속으로 밟았을 때와 아닐 때를 비교하여 더 큰 값을 선택하도록 해야함
*/

int main(int argc, char const* argv[])
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); // 속도 더 빠르게 해줌
    int num;
    cin >> num;
    vector<int> stair(num + 1, 0); // 입력받기
    vector<pair<int, int>> score(num + 1, { 0, 0 });; // vector<pair<int, int>> 초기화
    for (int i = 1; i <= num; i++) {
        int n;
        cin >> n;
        stair[i] = n;
    }
    score[1] = { 1, stair[1] };
    score[2] = { 2, stair[1] + stair[2] };
    for (int i = 3; i <= num; i++) { // dp로 구하기
        int res_1 = -1;
        int res_2 = -1;
        if (score[i - 1].first < 2) {
            res_1 = score[i - 1].second + stair[i];
            score[i] = { score[i - 1].first + 1, res_1 }; // 넣어두기
        }
        if (score[i - 2].first <= 2) {
            res_2 = score[i - 2].second + stair[i];
        }
        if (res_2 > res_1) {
            score[i] = { 1, res_2 }; // 조건에 따라 수정하기
        }
    }
    cout << score[num].second;

    return 0;
}