2579 계단오르기

점화식으로 바로 접근해서 헷갈리는 부분이 많았다.

D[n] = Max(D[n-2),D(n-1) + S(n) 이런 형식을 가지고만 생각하면 풀기 너무 어려워진다.

경우의 수를 나누어야 한다.

제일 마지막 계단은 무조건 밟아야 하는 것과 세번 연속 오를 수 없다는 것을 기준으로 경우를 나눠야 한다.

두가지 경우로 나누어 생각.

즉,  점화식을 세울 때

O X O O  --> D[n-3] + S[n-1] + S[n] // 전전전칸까의 최대값 + 전계단 + 마지막 계단

? O X O   --> D[n-2] + S[n]  // 전전칸까지의 최대값 + 마지막 계단

코드:

#include <iostream>

/*

계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.

마지막 도착 계단은 반드시 밟아야 한다.

*/

using namespace std;

int S[301];

int D[301];

bool check[301];

int max(int a, int b){

return a > b ? a : b;

}

int main()

{

int N;

cin >> N;

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

{

cin >> S[i];

}

D[0] = S[0];  //1칸

D[1] = max(S[0] + S[1], S[1]);  //2칸올라가는 경우 -> 1+1 or 2칸 한번에

D[2] = max((S[0] + S[2]), (S[1] + S[2]));

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

{

D[i] = max((D[i - 2] + S[i]), (D[i - 3] + S[i-1] + S[i]));

}

cout << D[N-1];

system("pause");

return 0;

}