백준 2579 계단 오르기

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

2579번: 계단 오르기

 

<입력> 

 

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

 

<규칙>

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

<출력>

 

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

 

<후기>

전형적인 DP 문제, 혹시 DP를 처음 접한다면 연습문제로 적절한거 같다. 

규칙들을 이용해서 i번째 계단에서 얻을 수 있는 최대값을 구해, 해당 값을 통해 i+1, i+2 번째 계단의 최대값을 구하면 된다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <vector>
#include <algorithm>
#include <memory.h>

using namespace std;

int D1[301], D2[301], stair[301];

int main(void) {

	int n;

	stair[0] = D1[0] = D2[0] = 0;

	// 1. 계단은 한 번에 1개 또는 2개씩 오를 수 있다.
	// 2. 연속된 3개의 계단을 모두 밟아서는 안 된다.
	// 3. 마지막 도착 계단을 밟아야 한다.

	// DP + 연속 계단 개수 고려
	scanf("%d", &n);

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

	if (n == 1) {
		printf("%d", stair[1]);
		return 0;
	}

	// 한칸 연속 불가능 (i-1번재 칸에서 한칸 전진해서 도달) 
	D1[1] = stair[1]; D1[2] = stair[1] + stair[2];
	// 가능 (i-2번째 칸에서 2칸 전진해서 도달)
	D2[1] = 0; D2[2] = stair[2];

	for (int i = 3; i <= n; i++) {
		D1[i] = D2[i - 1] + stair[i];
		D2[i] = max(D1[i - 2], D2[i-2]) + stair[i];
	}

	printf("%d", max(D1[n], D2[n]));


	return 0;
}