[C++] 백준 2579. 계단 오르기

🌽 문제

🥕 입출력

🥔 풀이

규칙을 꼬아보면 코드로 구현 가능한 두 가지 규칙을 알아낼 수 있다.

1. 계단 하나를 건너뛰었다면, 그 다음 계단은 무적권 밟아야 한다.
2. 두 개의 계단을 연속으로 밟았다면, 그 뒷 계단을 밟을 수 없다
   = 연속으로 밟은 두 계단의 직전 계단은 밟지 않았다.

for문에서 위 두 가지 규칙이 구현되었다.

🥬 코드

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, arr[300], dp[300] = { 0, };
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];

	dp[0] = arr[0];
	dp[1] = arr[0] + arr[1];
	dp[2] = arr[2] + max(arr[0], arr[1]);
	for (int i = 3; i < n; i++) {
		dp[i] = arr[i] + max(dp[i - 3] + arr[i - 1], dp[i - 2]);
	}
	cout << dp[n - 1];
	return 0;
}

🥜 채점