[백준] 2579 계단 오르기

백준2574 계단오르기 바로가기

이 문제에는 규칙이 있는데,

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

한번에 세 계단은 밟을 수 없으며, 마지막 도착 계단은 반드시 밟아야 한다.

경우를 두가지로 나눌 수 있는데,

1) 직전 계단을 밟은 경우
dp[n]=dp[n-3]+arr[n-1]+arr[n]
2) 직전 계단을 밟지 않은 경우
dp[n]=arr[n]+dp[n-2]

최대값을 구하는 것이므로 점화식을 계속 계산해 비교해가면 된다.

C++ 코드

#include<iostream>
#include <cstdio>
using namespace std;

int max(int a, int b) {

	return a > b ? a : b;
}

int main() {
	int N;
	
	scanf("%d", &N);
	int *arr = new int[N + 1];
	int *dp = new int[N + 1];
	arr[0] = 0;
	dp[0] = 0;

	for (int i = 1; i <= N; i++) {
		int data;
		scanf("%d", &data);
		arr[i] = data;
	}

	for (int i = 1; i<=3 && i <= N; i++) {
		if (i != 3)
			dp[i] = arr[i] + dp[i - 1];
		else
			dp[i] = max(arr[i - 1] + arr[i], arr[i - 2] + arr[i]);
	}

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

	printf("%d", dp[N]);
	return 0;
}