[C++] 백준 2579번: 계단 오르기 (DP)

2579번: 계단 오르기

---

1. 문제 이해하기

 이 문제를 요약해보면

규칙에 따라 계단을 오를 때, 얻을 수 있는 점수의 최댓값을 구하여라.

 

라고 할 수 있습니다.

 

 여기서 주어진 규칙은 다음과 같습니다.

1. 계단은 한 번에 한 칸 또는 두 칸을 오를 수 있다.
2. 시작점을 제외하고 연속 세 개의 계단은 밟을 수 없다.
3. 마지막 계단은 반드시 밟아야 한다.

 

 문제의 목표와 주어진 규칙을 숙지했다면, 다음 단계로 넘어가겠습니다. 

---

2. 시간복잡도 어림하기

모든 경우의 수 탐색 알고리즘 (브루트 포스 알고리즘)

 가장 단순하게, 모든 경우의 수를 탐색한다면 시간복잡도가 얼마나 될까요?

 

 그 답은..

 

 

 

 저도 잘 모르겠습니다!

 수학적으로 계산해 보려고 했지만, 제 수학 실력으로는 부족했네요..ㅠ

 

 그 대신,

 모든 경우의 수를 탐색하고자 할 때, 함수가 몇 번이 호출이 되는지 직접 알아보았습니다.

#include<iostream>
using namespace std;

int cnt, n;
void func(int pos, int hop){
    if(pos > n) return;
    if(pos == n){
    	cnt++; return;
    }
    if(hop == 1){ //이전에 두 칸 이동한 경우
        func(pos + 1, 0);
        func(pos + 2, 1);
    }
    else //이전에 한 칸 이동한 경우
    	func(pos + 2, 1);
}
int main(){
    cin >> n;
    func(1, 1); func(2, 1);
    cout << cnt;
    return 0;
}

 코드 설명을 간단히 하면, func 함수를 호출하여 n번 계단에 도달하는 경우의 수가 몇 가지 인지 출력하는 코드입니다.

 

 main 함수에서 func(1, 1), func(2, 1) 두 번에 걸쳐 실행하는 이유는 문제의 2번 조건인 시작점을 제외하고 연속 세 개의 계단을 밟을 수 없다라는 조건 때문입니다.

 

 시작점에서 계단을 오른다고 생각하지 않고, 1번 계단에서 시작하는 경우와 2번 계단에서 시작하는 경우로 나누어 구하는 것이 더 편해 이와 같은 방식으로 구현했습니다.

 

 위 코드를 실행해 보면, 다음과 같은 결과를 얻을 수 있습니다.

입력	출력
60	20330163

 

 문제에서 계단의 수(n)의 범위는 최대 300인데, n = 60임에도 불구하고 경우의 수가 2천만이 넘습니다.

 경우의 수가 2천만이 넘는다는 말은 이를 구하기 위한 함수 호출은 2천만보다 더 많다는 것을 의미합니다.

 

 따라서, 제한 시간 내에 이 문제를 해결하기에 브루트 포스 알고리즘은 적절하지 않습니다.

 

DP를 사용한 알고리즘

 DP를 사용했을 때의 시간복잡도를 구하기 전에,DP를 사용하는 것이 좋을 것 같다고 생각한 근거는

 1. 여러 경우의 수를 탐색 해야하고,

 2. 경우의 수가 너무 크고,

 3. 현재 상태와 이전 상태를 배열에 담을 수 있기 때문입니다.

 

 DP를 사용하면 한 번의 탐색으로 알고리즘을 마칠 수 있기 때문에 시간복잡도는 N입니다.

 이 문제에서 N의 최댓값이 300이기 때문에 시간복잡도는 300 정도가 되겠네요.

 

 시간복잡도가 300이면 상한선인 천만보다 낮은 수치이므로 DP를 사용하여 문제를 해결하도록 하겠습니다.

---

3. 알고리즘 설계하기

 알고리즘을 설계하기 전에, 문제의 조건을 다시 살펴보겠습니다.

1. 계단은 한 번에 한 칸 또는 두 칸을 오를 수 있다.
2. 시작점을 제외하고 연속 세 개의 계단은 밟을 수 없다.
3. 마지막 계단은 반드시 밟아야 한다.

 

 1번 조건에 의해 어떤 위치 pos에서 오를 수 있는 다음 계단의 위치는 pos + 1 또는 pos + 2입니다.

 반대로 생각하면, 현재 위치 pos에 도달할  수 있는 계단의 위치는 pos - 1 또는 pos - 2입니다.

 

 여기서 2번 조건까지 고려하면, 계단을 한 칸 오르기 위해서는 반드시 이전에 두 칸을 올라야 합니다.

 

 아래 그림을 보면,

 현재 위치 pos에 도달할 수 있는 경우의 수는

 pos - 2에서 두 칸을 올라 pos에 도달하거나,

 pos - 3에서 두 칸을 올라 pos - 1에 도달하고, pos - 1에서 한 칸을 올라 pos에 도달하는 두 경우 뿐입니다.

 

 이를 DP로 구현하면, (dp배열에는 현재 위치에서 얻을 수 있는 최대 점수를 담고있습니다.)

dp[i] = max(dp[i - 2] + score[i], dp[i - 3] + score[i - 1] + score[i]);

과 같이 나타낼 수 있습니다.

 여기서 + score[i]는 공통 부분이므로 밖으로 빼서 표현할 수 있겠네요.

---

4. 알고리즘 구현하기

 최종적으로 구현한 알고리즘 코드는 다음과 같습니다.

#include<iostream>
using namespace std;

int n, a[304], dp[304];
int main(){
    cin >> n;
    
    //a는 점수를 담는 배열입니다.
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    dp[1] = a[1];
    dp[2] = a[1] + a[2];
    for(int i = 3; i <= n; i++){
        dp[i] = max(dp[i - 2], dp[i - 3] + a[i - 1]) + a[i];
    }
    cout << dp[n];
    return 0;
}

 dp[i - 2]와 dp[i - 3]에 접근하기 위해서는 i가 3이상이어야 하므로 i = 3부터 시작합니다.

 

 누락된 i = 1과 i = 2는

dp[1] = a[1];
dp[2] = a[1] + a[2];

로 직접 값을 넣어 dp 값이 잘 갱신되도록 초기화 해주었습니다.

 

 참고로 위 코드에서는 배열의 인덱스를 1부터 초기화 했는데, 0부터 시작해도 상관없습니다.

 0부터 시작하기 원한다면, 범위에 주의해주세요!

---