백준 2579번 계단 오르기

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

2579번: 계단 오르기

풀이

 

먼저 DP배열을 정의합니다. 

 

DP[i번째발판에 있는 상태] //i번째까지 도달하는데 얻은 최대 점수

 

점프를 통해서 i번째 발판을 밟는 방법은 2가지가 있습니다.

 

1. (i-3)번 발판을 밟고 -> (i-1)번 발판을 밟고 -> i번 발판을 밟는다.

2. (i-2)번 발판을 밟고 -> i번 발판을 밟는다.

 

해당 방법들로 점화식을 짜게 된다면

 

Arr : 계단의 점수를 담은 배열 DP : i번계단까지 밟았을때의 최대 점수

DP[i] = max(DP[i - 3] + Arr[i - 1] + Arr[i], DP[i - 2] + Arr[i]);

  

1번 방법에서 점프를 두 번이나 하면서 발판을 밟는 이유는

 

3개의 계단을 연속해서 밟으면 안되기 때문입니다!!

 

 

(i-1) -> i 나 (i-2) -> (i-1) -> i 순서로 이동하면 3개의 계단을 연속해서 밟은 것이 되기 때문입니다.

 

코드

 

#include <bits/stdc++.h>

using namespace std;

#define endl "\n"
#define int long long
#define float double

#define MAX 10001

int N;
int DP[MAX]; //i번 계단까지 밟았을때의 최대 점수
int Arr[MAX]; //i번 계단의 점수

int32_t main()
{
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	std::cout.tie(NULL);
	
	cin >> N;

	for (int i = 1; i <= N; i++)
		cin >> Arr[i];

	DP[0] = 0;
	DP[1] = Arr[1];
	DP[2] = Arr[1] + Arr[2];
	

	for (int i = 3; i <= N; i++)
    	//DP 점화식
		DP[i] = max(DP[i - 3] + Arr[i - 1] + Arr[i], DP[i - 2] + Arr[i]);

	cout << DP[N] << endl;

	return 0;
}

 

-----------------------------------------------------------------------------------------------------------------------------------

질문은 언제나 환영합니다.