[BOJ] 2579 계단오르기 C++

개요

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

실버급 DP 문제다.

본문

풀이

2차원 배열인 dp에 점수를 저장했다.

dp[계단번호][연속이동횟수]

중복되는 부분은 함수로 처리했다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
constexpr int RANGE = 302;

int GetMaxDP(int* dp) {
	int max = (dp[1] > dp[2]) ? dp[1] : dp[2];
	return max;
}

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

	// 최대 값을 기억할 변수
	int dp[RANGE][3] = { 0 };
	int stair[RANGE] = { 0 };
	int n = 0;

	cin >> n;
	for (int i = 1; i <= n; i++) 
		cin >> stair[i];
	
	// 초기값
	dp[1][1] = stair[1];
	for (int i = 2; i <= n; i++)
	{
		// 1회 연속 이동의 경우, -2계단의 이동 값 중 큰 값을 더함
		dp[i][1] = GetMaxDP(dp[i - 2]) + stair[i];
		// 2회 연속 이동의 경우, -1계단의 1회 연속 이동 값을 더함
		dp[i][2] = dp[i - 1][1] + stair[i];
	}

	cout << GetMaxDP(dp[n]);
}

결론

풀이를 생각하는 데에 꽤 많은 시간이 소요됐다.

DP 문제는 계속해서 많이 풀어봐야 할 것 같다.