dp 백준 2579 계단 오르기

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

2579번: 계단 오르기

이상에서 계단을 정말 특이하게 오르는 사람이 있다 왜저렇게 오르는지 ;;;; 할튼 문제에서는 계단을 한번에 한 계단씩 또는 두계단씩 오를 수 있다. 하지만 연속 세 개의 계단을 모두 밟을 수 없다????? 지뢰가 있나보다!!! 그리고 마지막 계단을 꼭 밟아야 한다고 한다. 

 

요약하면 

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 

2. 연속된 세개의 계단을 모두 밟아서는 안된다. (시작 점 제외)

3. 마지막 계단을 밟아야한다. 

 

이 문제는 i 번째 독착할 때의 방법에 집중해보면 된다. i번째 계단에 도착하려면 연속해서 두번 밟는 경우 또는 점프해서 밟는 경우이다. 

dp[i] = dp[i-3] + arr[i-1] + arr[i]; // 연속 두번 밟는 경우 
dp[i] = dp[i-2] + arr[i]; // 점프해서 밟는 경우

연속 두번 밟으면  i, i-1의 값을 더해주면서 두번 밟았다는 것은 i-1에 점프를 해서 왔다는 내용이기 때문에 i-3의 최대 값을 더해준다. 

점프해서 밟는 경우는 i-2 2개전의 계단에서 출발했다는 의미이며 i번째 값을 더해준 것이기 때문에 위와 같은 점화식이 나온다. 

#include <stdio.h>
#include <algorithm>

using namespace std;

int N;
int arr[100002];
int dp[100002];
int main(){
	scanf("%d", &N);

	for(int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	dp[0] = arr[0];
	dp[1] = arr[0] + arr[1];
	dp[2] = max(arr[2] + arr[0], arr[1] + arr[2]);

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

	printf("%d", dp[N-1]);
}