백준 2579 (DP)

2579번: 계단 오르기

과정

• 처음에는 그래프인가 했다가 이것도 계단 오르는 규칙이 있는 문제이므로 DP를 이용해서 풀어보려고 했다.

• 계단을 오르는데는 2가지 규칙이 있다.
  1. 연속된 2개 계단 오르기
  2. 한 칸만 건너뛰기
  즉, 현재 내가 서있는 칸(N)을
  연속된 2번째 계단으로 만들건지,(N-1을 밟은 상태) 한칸 건너뛴 계단으로 만들건지(N-1을 안밟은 상태)
  결정해야 한다.
• 따라서, DP[N] = max(DP[N-3] + Arr[N-1] + Arr[N], DP[N-2] + Arr[N])
• 또한, max값을 보면, 전부 자신의 계단을 포함하는 것을 알 수 있다. 그렇기 때문에 DP값을 사용한다는 것은 DP의 인덱스에 해당하는 계단을 밟았다는 의미가 된다.
• 위 식을 해석하면, N번째 계단의 최대값은
  1. DP[N-3] + Arr[N-1] + Arr[N] : N-3을 밟고, 한칸 뛰고 N-1, N번째 계단을 연속을 밟는다.
  2. DP[N-2] + Arr[N] : N-2을 밟고, 한칸 뛰고 N번째 계단을 밟는다
  로 구할 수 있다.

코드

#include <iostream>

using namespace std;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(NULL);

    int N = 0;      // 총 계단 개수

    int Arr[301];   // 계단 개수는 300 이하 이므로

    int DP[301];    // N번째 계단에서의 최대값

    cin >> N;

    for (int i = 1; i < N + 1; i++)

    {

        cin >> Arr[i];

    }

    DP[1] = Arr[1];

    DP[2] = Arr[1] + Arr[2];

    DP[3] = max(Arr[1] + Arr[3], Arr[2] + Arr[3]);

    for (int i = 4; i < N + 1; i++)

    {

        DP[i] = max(DP[i-3] + Arr[i-1] + Arr[i], DP[i-2] + Arr[i]);

    }

   

    cout << DP[N];

    return 0;

}

 

문제의 조건인 "마지막 도착 계단은 반드시 밟아야 한다." 또한, DP값을 출력하므로서 이미 N번째 칸을 밟았다는 뜻이므로조건을 만족시킨다.