88. 백준 2579 번 C++ 코드 및 자세한 설명

안녕하세요 코딩하는 덕구입니다.

다이나믹 프로그래밍 알고리즘 문제인 BOJ 2579 번 계단 오르기 입니다.

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

2579번: 계단 오르기

 

 

백준 2579 번 C++ 정답 코드입니다. 설명은 아래에 있습니다.

#include <iostream>
#define MAX 301
using namespace std;
int stair[MAX] = {0,};
int DP[MAX] = {0,};

int main(){
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> stair[i];

    if (N <= 2){
        int sum = 0;
        for (int i = 0; i < N; i++){
            sum += stair[i];
        }
        cout << sum;
    }
    else{
        for (int i = 0; i < N; i++){
            DP[i] = max(DP[i - 2] + stair[i], DP[i - 3] + stair[i] + stair[i - 1]);
        }
        cout << DP[N - 1];
    }

    return 0;
}

 

문제 요약

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
   즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

총 3가지의 규칙을 지키면서 계단을 밟으면서 생기는 최대 점수를 구하는 문제입니다.

 

문제 접근

지금까지의 계단 점수 중 위의 조건을 지키면서 가장 높은 점수들을 저장했다고 가정한다면

마지막 도착 계단을 E 라고 했을 때, 계단은 한칸 or 두칸을 지날 수 있으므로

E를 밟기위해서는 E - 1 혹은 E - 2 계단 중 더 높은 점수를 가진 계단을 밟으면 되는데

 

1. 만약 [ E - 2 ] 계단이 점수가 더 높다면 E - 2의 계단을 밟아주면 되고

 

2. 만약 [ E - 1 ] 계단이 점수가 더 높다면 다음 계단은 1칸만 오를 수 있으므로

[ E - 2 ] 를 밟지 않고 얻은 [ E - 1 ] 까지의 계단 점수를 구해서 더해주면 됩니다.

즉 [E - 3] + [E -1] 이 되겠죠 (1칸 아니면 2칸으로 이동 가능)

 

C++ 코드 구현

먼저 계단의 모든 점수들을 입력받아 저장합니다.

for (int i = 0; i < N; i++) cin >> stair[i];

 

그리고 i번째 계단 까지의 누적 최대 점수를 저장할 행렬인 DP 를 선언하고,

 Base Case를 작성합니다. 앞서 우리가 구한 공식에서 i 번 째 계단을 구하기 위해 i - 3 까지 사용했으므로

i 를 식으로 구하기 위해서는 i - 3 까지가 저장되어야 있어야 됩니다.

 즉 최소 3개의 Base Case 가 필요합니다.

0번 계단까지의 최대 누적 점수는 stair[0]

1번 계단까지의 최대 누적 점수 = stair[0] + stair[1]

2번 계단까지의 최대 누적 점수 = max(stair[2] + stair[0], stair[2] + stair[1])

DP[0] = stair[0];
DP[1] = stair[0] + stair[1];
DP[2] = max(stair[0] + stair[2], stair[1] + stair[2]);

 

그리고 사전에 구한 공식을 적용하여 i번째 계단까지의 최대 누적 점수를 계산합니다.

for (int i = 3; i < N; i++){
    DP[i] = max(DP[i - 2] + stair[i], DP[i - 3] + stair[i] + stair[i - 1]);
}

 

이제 출력하면 됩니다.

cout << DP[N - 1];

 

이 문제에서는 N이 300이하의 자연수이므로 예외처리를 해줍시다.

N <= 2 일때 BASE CASE를 만들지 않고, 그냥 더해서 출력하는 식으로 구현했습니다.

if (N <= 2){
    int sum = 0;
    for (int i = 0; i < N; i++){
        sum += stair[i];
    }
    cout << sum;
}

 

백준 2579 번 계단 오르기 C++ 최종 코드입니다.

#include <iostream>
#define MAX 301
using namespace std;
int stair[MAX] = {0,};
int DP[MAX] = {0,};

int main(){
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> stair[i];

    if (N <= 2){
        int sum = 0;
        for (int i = 0; i < N; i++){
            sum += stair[i];
        }
        cout << sum;
    }
    else{
        DP[0] = stair[0];
        DP[1] = stair[0] + stair[1];
        DP[2] = max(stair[0] + stair[2], stair[1] + stair[2]);

        for (int i = 3; i < N; i++){
            DP[i] = max(DP[i - 2] + stair[i], DP[i - 3] + stair[i] + stair[i - 1]);
        }
        cout << DP[N - 1];
    }

    return 0;
}

 

제가 운영하는 오픈 카톡방입니다. 알고리즘, 코딩, 취업정보 등 자유롭게 질문, 답변 및 대화 나눠요.

https://open.kakao.com/o/guGhqGAg

알고리즘, 코딩, 개발자 취업 질문방 (비번 4321)

 

백준 2579 번 계단 오르기 자세한 설명 및 C++ 코드였습니다.

감사합니다.