BOJ-2579-계단 오르기

[changicho]

2579. 계단 오르기

링크

난이도	정답률(_%)
Silver III	39.376

설계

점화식

dp[1] = stairs[1];
dp[2] = stairs[1] + stairs[2];

dp[i] = stairs[i] + max(dp[i - 3] + stairs[i - 1], dp[i - 2]);

정리

내 코드 (ms)	빠른 코드 (ms)
0

고생한 점

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using namespace std;

vector<int> stairs;
vector<long long> dp;

void solution() {
	int N;

	cin >> N;

	stairs.resize(N + 1);
	dp.resize(N + 1);

	for (int i = 1; i <= N; i++) {
		cin >> stairs[i];
	}

	dp[1] = stairs[1];
	dp[2] = stairs[1] + stairs[2];

	for (int i = 3; i <= N; i++) {
		dp[i] = stairs[i] + max(dp[i - 3] + stairs[i - 1], dp[i - 2]);
	}

	cout << dp[N] << "\n";
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}