챕터3-17. DP | 문제 풀이3 - (6) 백준 No.2579 : 계단 오르기

연속합 문제

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

문제요약

* 2156번 포도주 시식 문제랑 비슷하게 생각하면 된다. 그냥 숫자가 나열된 문제로 볼 수 있음.

 

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다.
각 계단에는 점수가 쓰여 있는데, 올라가면서 계단을 밟으면 계단에 쓰여있는 점수를 얻게 된다.
계단을 오르는 데는 다음과 같은 규칙이 있다.
1) 계단은 한 번에 한 계단 혹은 두 계단씩 오를 수 있다. (즉, 한 계단을 밟으면 이어서 다음 계단이나 다다음 계단으로 오를 수 있다.)
2) 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
3) 마지막 도착 계단은 반드시 밟아야 한다.

ex) s 10 20 15 25 10 20

해결 방법1(2차원 배열 이용)

1. D[i][j] 정의
D[i][j] = "i번째 계단에 올라갔을 때의 최대점수이며, i번째 계단은 j개 연속해서 올라온 계단임)"

j의 값에 따라서 아래와 같은 케이스들이 존재한다.
j = 0(i번째 위치가 0번연속해서 올라온 계단인 경우),
j = 1(i번째 위치가 1번연속해서 올라온 계단인 경우), 
j = 2(i번째 위치가 2번연속해서 올라온 계단인 경우)

정답은 D[n][0], D[n][1], D[n][2] 중 최대값이 된다. 즉, max (D[n][0], D[n][1], D[n][2])

각각의 값은 아래의 식을 세워 구할 수 있게 된다.

 

2. 각 케이스에 따른 점화식 세우기

case 1) D[i][0]  = i번째 계단이 0번 연속해서 올라온 계단인 경우(...X)
=> D[i][j]의 정의상 i번째 계단에 올라가있는 상태이어야 하는데, 
       D[i][0] 는 i번째 계단에 올라가 있지 않음을 의미하므로 이는 사용할 수 없음. 따라서, 사용 안함

case 2) D[i][1]  = i번째 계단이 1번 연속해서 올라온 계단인 경우(....XO|XO  또는  ....OO|XO)
=> i번째 계단은 밟음, i-1번째 계단은 안 밟음, i-2번째 계단은 j = 1인 상태이거나 j = 2인 상태일테니 둘 중 최대값 선택.
D[i][1] = max (D[i-2][1], D[i-2][2]) + A[i]

case 3) D[i][2]  = i번째 계단이 2번 연속해서 올라온 계단인 경우(....XO|XOO 또는 ....OO|XOO)

=> i번째 계단은 밟음, 반드시 i-1번째 계단은 j = 1인 상태 이어야함(1개 연속해서 올라온 계단)

D[i][2] = D[i-1][1] + A[i]                    -> 여기서 D[i-3] 에 대한 걸 처리하지 않는 이유는 D[i-1][1]에 그 과정이 포함되어 있기 때문.

 

정답은 D[n][1]과 D[n][2] 중의 최대값이 된다.

<Bottom-up 방식>

(1)시간복잡도
= for 문의 반복 횟수 

= O(N)

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

#include<iostream>

using namespace std;

int a[301];
int d[301][3];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    d[1][1] = a[1];
    d[1][2] = 0;

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

    for (int i = 3; i <= n; i++){
        d[i][1] = max(d[i-2][1], d[i-2][2]) + a[i];
        d[i][2] = d[i-1][1] + a[i];
    }

    cout << max(d[n][1], d[n][2]) << "\n";
}

해결 방법2(1차원 배열이용)

* 2차원 배열을 사용할 때와 차이점은 d[]를 점화식에서 사용할 때 max(case1, case2) 의미를 갖는다. 즉, 중첩된 의미를 가짐.

 

1. D[i] 정의
D[i] = "i번째 계단에 올라갔을 때의 최대 점수"

i번째 계단에 대해서는 아래와 같은 케이스들이 존재한다.

case 1) 올라간 i번째 계단이 1개 연속인 상태의 경우

case 2) 올라간 i번째 계단이 2개 연속인 상태의 경우

D[i] = max (case1, case2)가 되는 것이고 정답은 D[n]의 값을 얻으면 된다.

 

2. 각 케이스에 따른 점화식 세우기
case 1) 올라간 i번째 계단이 1개 연속인 상태의 경우(...XO|XO 또는 ....OO|XO)

=> i번째 계단은 밟음, i-1 번째 계단은 안 밟음, i-2는 case1이거나 case2인데 알아서 D[i-2]에 최대값이 들어있을 예정
D[i-2] + A[i]                                     * D[]는 case1 이거나 case2모두 가능한 곳일 때만 사용할 수 있음

case 2) 올라간 i번째 계단이 2개 연속인 상태의 경우(....XO|XOO 또는 ....XOO|XOO)

=> i, i-1번째는 무조건 밟고 i-2는 밟지 않으면서 i-3번째는 반드시 밟았어야 함(계단은 한 계단씩, 두 계단씩만 오를 수 있어서)
D[i-3] + A[i-1] + A[i]                         * D[]는 case1 이거나 case2모두 가능한 곳일 때만 사용할 수 있음

 

그러면 D[i] = max( D[i-2] + A[i], D[i-3] + A[i-1] + A[i] ) 이고 정답은 D[n]이 된다.

<Bottom-up 방식>

(1)시간복잡도
= for 문의 반복 횟수 

= O(N)

 

(2) 구현
-> 'for문을 이용한 반복문'으로 구현

#include<iostream>

using namespace std;

int a[301];
int d[301];

int main()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    d[0] = 0;
    d[1] = a[1];
    d[2] = a[1] + a[2];

    for (int i = 3; i <= n; i++)
        d[i] = max (d[i-2] + a[i], d[i-3] + a[i-1] + a[i]);

    cout << d[n] << "\n";
}