[백준 - 2579] 계단 오르기

#include <iostream>
#define MAX 301
using namespace std;
#define Max(x,y) ((x) < (y) ? y : x)

int stairs[MAX];
int DP[MAX];

int main()
{
	//1. Get input
	ios::sync_with_stdio(0), cin.tie(0);
	int N; cin >> N;

	for (int i = 1; i <= N; ++i)
	{
		cin >> stairs[i];
	}

	//2. Set initial value
	DP[1] = stairs[1];
	DP[2] = stairs[1] + stairs[2];
	DP[3] = Max(stairs[1],stairs[2]) + stairs[3];

	//3. Solve
	for (int i = 0; i <= N; i++)
	{
		DP[i] = Max(DP[i - 2], DP[i - 3] + stairs[i - 1]) + stairs[i];
	}

	//4. Print
	cout << DP[N] << "\n";
}

---

||사용 기법

• DP

---

||풀면서 느낀 것

• DP의 응용

이 문제는 여러 형식으로 풀수 있었는데 이걸 통해 여러가지로 사고 방식을 배웠다.

• DP

조금 DP문제를 풀어보면서 약간 똑똑한 브루트 포스 느낌을 받았다.

그래서 이걸 DP로 풀어야하는지 약간 감이 생겼다.