[C++] 백준 2579번 계단 오르기

 

1) 문제설명

백준 Onlie Judge 2579번 계단 오르기

 

2) 아이디어

bottom - up 구조의 for문 DP사용
d [0] = 첫 번째 계단
d [1] = 첫 번째 계단 + 두 번째 계단
d [2] = 첫 번째 계단 + 두 번째 계단 or 두번째 계단 + 세 번째 계단 중에 큰 것.
d [i] = i-2번째 계단까지의 최대 + i번 계단 or i-3번째 계단까지의 최대 + i-1번째 계단 + i번째 계단.

3) 코드

int main() {
	int n;
	int* arr;
	cin >> n;
	arr = (int*)malloc(sizeof(int) * n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	d[0] = arr[0]; // 10
	d[1] = arr[0] + arr[1];
	d[2] = max(arr[0] + arr[2], arr[1] + arr[2]);

	for (int i = 3; i < n; i++) {
		d[i] = max(d[i - 2] + arr[i], d[i - 3] + arr[i - 1] + arr[i]);
	}
	cout << d[n - 1];
}