[Baekjoon Online Judge] 백준 2579번 계단 오르기(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 2579번 계단 오르기

(C++, Python)

(글쓴날 : 2020.04.12)

 

---

* Baekjoon Online Judge, 백준 2579번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 2579번 계단 오르기

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

---

2) 풀이 과정

밟으면 점수가 올라가는 계단을 특정 규칙을 준수하며 마지막 계단까지 올라갈 때, 최종적으로 얻을 수 있는 최대 점수를 구하는 문제입니다.

특정 규칙은 3가지이며, 계단은 한 번에 한 계단 혹은 두 계단씩 오를 수 있고, 연속으로 세계단 이상을 밟아선 안되며, 마지막 계단은 반드시 밟아야 합니다.

 

저의 경우, 동적 계획법을 적용하여 문제에 접근하였으며, C++과 Python을 사용했습니다.

동적 계획법을 적용하기 위해 도출한 점화식은 memoization[i] = stairs[i] + stairs[i - 1] + memoization[i - 3] or memoization[i] = stairs[i] + memoization[i - 2]이며 최대 현재 인덱스의 -3까지 연산해야 하므로 0, 1, 2 번째 인덱스는 조건문으로 분기하여 따로 계산했습니다.

또한, 애초에 계단이 1개 혹은 2개가 들어올 경우 답을 바로 구할 수 있기 때문에, 즉시 답을 출력한 뒤 exit() 함수로 종료하는 예외 처리를 추가하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int stairNum = 0;
 
    cin >> stairNum;
 
    vector<int> stairs(stairNum, 0);
    vector<int> memoization(stairNum, 0);
 
    for (int i = 0; i < stairNum; i++)
        cin >> stairs[i];
 
    if (stairNum == 1)
    {
        cout << stairs[0];
        exit(0);
    }
    if (stairNum == 2)
    {
        cout << stairs[0] + stairs[1];
        exit(0);
    }
 
    for (int i = 0; i < stairNum; i++)
    {
        if (!i)
            memoization[0] = stairs[0];
        else if (i == 1)
            memoization[1] = stairs[0] + stairs[1];
        else if (i == 2)
        {
            if (stairs[0] + stairs[2] > stairs[1] + stairs[2])
                memoization[2] = stairs[0] + stairs[2];
            else
                memoization[2] = stairs[1] + stairs[2];
        }
        else
        {
            if (stairs[i] + stairs[i - 1] + memoization[i - 3] > stairs[i] + memoization[i - 2])
                memoization[i] = stairs[i] + stairs[i - 1] + memoization[i - 3];
            else
                memoization[i] = stairs[i] + memoization[i - 2];
        }
    }
 
    cout << memoization[stairNum - 1];
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
stairNum = int(input())
stairs = [int(input()) for _ in range(stairNum)]
memoization = [0] * stairNum
 
if stairNum == 1:
    print(stairs[0])
    sys.exit(0)
if stairNum == 2:
    print(stairs[0] + stairs[1])
    sys.exit(0)
 
for i in range(stairNum):
    if not i:
        memoization[0] = stairs[0]
    elif i == 1:
        memoization[1] = stairs[0] + stairs[1]
    elif i == 2:
        if stairs[0] + stairs[2] > stairs[1] + stairs[2]:
            memoization[2] = stairs[0] + stairs[2]
        else:
            memoization[2] = stairs[1] + stairs[2]
    else:
        if stairs[i] + stairs[i - 1] + memoization[i - 3] > stairs[i] + memoization[i - 2]:
            memoization[i] = stairs[i] + stairs[i - 1] + memoization[i - 3]
        else:
            memoization[i] = stairs[i] + memoization[i - 2]
 
print(memoization[-1])

---