백준 C++ | #22 BOJ2579 계단 오르기 C++ 문제 풀이

Computer Science/C++

백준 C++ | #22 BOJ2579 계단 오르기 C++ 문제 풀이

토마토. 2022. 8. 22. 11:25

2579번: 계단 오르기

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점

www.acmicpc.net

DP에서는 재귀 대신 배열이나 벡터를 이용해서 값을 저장한다.

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

int main() {
	int n;
	std::cin >> n;
	std::vector<int> v;
	std::vector<int> dp(301);

	for (int i = 0; i < n; i++) {
		int tmp;
		std::cin >> tmp;
		v.push_back(tmp);
	}

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