[백준] #2579 계단 오르기 - (DP)

문제

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

2579번: 계단 오르기

 

목표

가중치가 쓰인 계단이 있을때 마지막 계단까지 이동하며 얻을수 있는 최대 가중치 구하기(단, 3개연속 불가능)

 

풀이

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

즉 현재 위치한 계단에서 구해지는 최대 가중치는 현재 계단의 가중치 + max(전전 계단에서의 최대가중치, 전전전 계단에서의 최대 가중치 + 이전계단의 가중치)

   => 2칸 전에서 현재로 이동했을때의 가중치 VS 3칸전에서 현재이전계단, 현재계단을 밟을때의 가중치의 최대값이다.

 

코드

1. 재귀로 구현

////재귀로 구현
#include <iostream>
#include <cstring>
#define MAX 301

using namespace std;

int N;
int arr[MAX];
//dp[i]: i번째 계단에 올랐을때의 최대점수
int dp[MAX];
int func(int s) {
	//계단층수가 0보다 작으면 0리턴
	if (s < 0)
		return 0;
	int &ref = dp[s];
	if (ref != -1)
		return ref;
	//dp[i]: 전전계단에서 현재계단으로 온경우 VS 전전전계단에서 전계단으로, 현재계단으로 온경우
	ref = max(ref, func(s-2) + arr[s]);
	ref = max(ref, func(s-3) + arr[s-1] + arr[s]);
	return ref;
}
int main() {
	cin >> N;
	for (int i=0; i<N; ++i) {
		cin >> arr[i];
	}
	memset(dp, -1, sizeof(dp));
	// dp[0] = arr[0];
	// dp[1] = arr[0]+arr[1];
	// dp[2] = arr[0]+arr[2];
	cout << func(N-1);
	// cout << '\n' << '\n';
	// for (int i=0; i<N; ++i) {
	// 	cout << dp[i] << '\n';
	// }
}

 

2. 반복으로 구현

#include <iostream>
#include <vector>
#define MAX 301

using namespace std;

int N;
int dp[MAX];
int arr[MAX];

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