[2579] 계단 오르기

• 입력: 계단의 수 N(N는 300이하의 자연수), N개의 계단 점수(계단 점수는 10,000이하)
• 출력: 마지막 계단을 밟고 나서 최대 총합
• 조건: 1) 한 칸 혹은 두 칸을 뛸 수 있다  2) 연속으로 세칸을 밟을 수 없다 3) 마지막 계단은 무조건 밟아야 한다
• 실패한 소스코드
?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std;   int main() {     int N;     scanf("%d", &N);       vector<int> step(N + 1), dp(N + 1);     step[0] = dp[0] = 0;     for (int i = 1; i <= N; i++)         scanf("%d", &step[i]);       dp[1] = step[1];     bool isJump = false;     for (int i = 2; i <= N; i++) {         if (isJump || dp[i - 1] < dp[i - 2]) {   //두칸             dp[i] = dp[i - 2] + step[i];             isJump = false;         }         else {                                  //한칸             dp[i] = dp[i - 1] + step[i];             isJump = true;         }     }       printf("%d\n", dp[N]);     return 0; }

한칸을 뛰면 무조건 다음 턴에서는 두칸을 뛰어야하는데 그것이 틀렸던 것 같다.
• 성공한 소스코드
?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#define _CRT_SECURE_NO_WARNINGS #include <cstdio> #include <vector> using namespace std;   int max(int a, int b) { return (a > b ? a : b); }   int main() {     int N;     scanf("%d", &N);       vector<int> step(N + 1), dp(N + 1);     step[0] = dp[0] = 0;     for (int i = 1; i <= N; i++)         scanf("%d", &step[i]);       for (int i = 1; i <= 3 && i <= N; i++)         if (i != 3)             dp[i] = dp[i - 1] + step[i];         else             dp[i] = max(step[i] + dp[i - 2], step[i] + step[i - 1]);       for (int i = 4; i <= N; i++)         dp[i] = max(step[i] + dp[i - 2], step[i] + step[i - 1] + dp[i - 3]);       printf("%d\n", dp[N]);     return 0; }

해당 칸에서 지난 계단을 밟았는지, 밟지 않았는지 두가지 경우로 나뉘어 최댓값을 저장한다.

• 문제 참고:https://www.acmicpc.net/problem/2579