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

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

2579번: 계단 오르기

첫번째 계단일 때와 두번째 계단일 때는 고민 없이 구할 수 있다.

 

하지만 세번째 계단부터는 연속해서 3개 계단을 오를 수 없는 규칙이 있기 때문에 고민을 해야한다.

세번째 계단을 오르기 위해서는

1. 시작 -> 첫번째 계단 -> 세번째 계단

2. 두번째 계단 -> 세번째 계단 

이렇게 두가지 경우가 있다.

 

이 중 더 큰 한가지를 선택해야되기 때문에 max(1,2) 이렇게 볼 수 있다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int n;
	cin >> n;

	int arr[301] = {};

	arr[0] = 0;	//시작점 = 0

	for (int i = 1; i <= n; i++) {
		cin >> arr[i];
	}
	int dp[301] = {};

	dp[0] = 0;
	dp[1] = arr[1];
	dp[2] = arr[2] + arr[1];
	
	for (int i = 3; i <= n; i++) {
		dp[i] = max(dp[i - 3] + arr[i - 1] + arr[i], dp[i - 2] + arr[i]);	//dp[i-1]에 이미 arr[i-3] 포함됨.
		//ex) i=4 max(dp[1] + arr[3] + arr[4], dp[2] + arr[4]) -> dp[2]에 이미 arr[1] 포함됨
	}

	cout << dp[n];
}

이렇게 구현하는거 넘나 어려운것 ㅜ..공식 생각하면서 한번씩 뇌정지 오는건 선택이 아닌 필수임