[c++] 백준 2579 계단 오르기

백준 단계별로 풀어보기 [동적계획법1] 계단 오르기

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

2579번: 계단 오르기

 

[풀이]

계단은 한번에 한계단 또는 두계단을 올라야 하며, 연속된 세 계단을 모두 밟으면 안된다. 마지막 계단은 반드시 밟아야한다. 즉 목표계단을 중심으로 목표계단과 그 전 계단을 밟은 경우, 목표계단과 그로부터 2단계 전 계단을 밟은 경우를 계산해주면 된다. 

예를 들어, 6번째 계단을 오르는 점수의 최댓값은 <3번째 계단을 오르는 점수의 최댓값 + 4번째 계단을 오르지 않고 5, 6번째 계단을 연속으로 오르는 경우> 또는 <4번째 계단을 오르는 점수의 최댓값 + 5번째 계단을 오르지 않고 두 계단 건너 6번째 계단을 오르는 경우> 중 더 큰 값이 된다. 

-> m[]을 1~n계단까지 오르는 점수 합의 최댓값을 저장, stair[]에 1~n계단까지의 각각의 점수를 저장하는 배열로 한다.

m[6] = m[3] + stair[5] + stair[6] 또는 m[6] = m[4] + stair[6] 중 더 큰 값이 m[6]에 저장된다.

 

[코드]

#include <iostream>
#include <string>
#include <algorithm>

int stair[301];
int m[301];

int main() {
	int n;
	std::cin >> n; //계단의 개수
	for (int i = 1; i <= n; i++) {
		std::cin >> stair[i];
	}

	m[0] = 0;
	m[1] = stair[1];
	m[2] = m[1] + stair[2];

	for (int i = 3; i <= n; i++) {
		//m[5] = m[2] + stair[4] + stair[5] or m[5] = m[3] + stair[5]
		m[i] = std::max(m[i - 3] + stair[i - 1] + stair[i], m[i - 2] + stair[i]);
	}

	std::cout << m[n];

	return 0;
}