[Olympiad] 지역본선 2006 초등부 : 계단 오르기 #2579

문제 출처

계단 오르기

문제 요약

• 계단 오르는 데는 다음과 같은 규칙이 있다.
  1.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
  2.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
  3. 마지막 도착 계단은 반드시 밟아야 한다.
• 따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다.
• 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

첫 번째 접근

• n-3까지만 구하고 n-2 n-1 n을 따로 더해주려고 했다.

    memo[1] = input[1];
    memo[2] = input[1] + input[2];
    for (int i = 3; i <= n-3; i++) {
        memo[i] = memo[i-1]; // OOX
        if (memo[i] < memo[i - 2] + input[i]) {
            memo[i] = memo[i - 2] + input[i]; // OXO
            flag = 1;
        }
        if (memo[i] < memo[i - 3] + input[i - 1] + input[i]) {
            memo[i] = memo[i - 3] + input[i - 1] + input[i]; // XOO
            flag = 2;
        }
        if (memo[i] == memo[i - 1])
            flag = 0;
    }
    memo[n] = memo[n - 3] + input[n];
    if (flag == 2) 
        memo[n] += input[n - 1];
    else {
        if (input[n - 2] > input[n - 1])
            memo[n] += input[n - 2];
        else
            memo[n] += input[n - 1];
    }
    cout << memo[n] << '\n';
    return 0;
  }

• 반례 : 10 20 15 25 10 20일 때
• 20 15 10 20을 가져가서 최대값이 안나온다.

  두 번째 접근

• n-1까지 구하고 flag값에 따라 처리

    memo[1] = input[1];
    memo[2] = input[1] + input[2];
    for (int i = 3; i <= n-1; i++) {
        memo[i] = memo[i-1]; // OOX
        if (memo[i] < memo[i - 2] + input[i]) {
            memo[i] = memo[i - 2] + input[i]; // OXO
            flag = 1;
        }
        if (memo[i] < memo[i - 3] + input[i - 1] + input[i]) {
            memo[i] = memo[i - 3] + input[i - 1] + input[i]; // XOO
            flag = 2;
        }
        if (memo[i] == memo[i - 1])
            flag = 0;
    }
    memo[n] = input[n];
    if (flag == 2) {
        if (input[n - 1] > input[n - 2])
            memo[n] += memo[n - 1] - input[n - 2];
        else
            memo[n] += memo[n - 2];
    }
    else
        memo[n] = memo[n - 1] + input[n];
    cout << memo[n] << '\n';
    return 0;
  }

• 반례 : OOX가 나올 수가 없다.
• X라는게 있을 수가 없다. 문제를 잘못 이해함.

  코드 설명

• memo[i][1]은 계단을 건너뛴 합을 대입한다.
  ex) memo[3][1]은 1번째 계단 O 2번째 계단 X 3번째 계단 O
• memo[i][2]은 계단을 연속적으로 밟은 합을 대입한다.
  ex) memo[3][2]은 1번째 계단 X 2번째 계단 O 3번째 계단 O
• memo[i][1]은 memo[i-2][1]과 memo[i-2][2]중 최대값을 구해 input[i]를 더해준다.
• memo[i][2]은 memo[i-1][1]에 input[i]를 더해준다.

문제 해답

#include <iostream>
using namespace std;
const int MAX = 301;
int memo[MAX][3];
int input[MAX];
int max(int a, int b);
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> input[i];
    memo[1][1] = input[1];
    for (int i = 2; i <= n; i++) {
        memo[i][2] = memo[i - 1][1] + input[i];
        memo[i][1] = max(memo[i - 2][1], memo[i - 2][2]) + input[i];
    }
    cout << max(memo[n][1], memo[n][2]) << '\n';
    return 0;
}

int max(int a, int b) {
    if (a > b)
        return a;
    else
        return b;
}