[2579] 계단 오르기

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

한칸을 뛰면 무조건 다음 턴에서는 두칸을 뛰어야하는데 그것이 틀렸던 것 같다.
• 성공한 소스코드
#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