BOJ 2579 - 계단 오르기 / C++

문제 링크 : https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

 

문제 풀이

DP를 이용하여 푼다. 우선 1번 계단과 2번 계단의 최댓값은 모든 계단을 밟으면 되므로 그대로 초기화해준다.

3번 계단부터는 경우가 여러 개로 나뉘어진다.

(1). 1번 계단 -> 3번 계단

(2). 2번 계단 -> 3번 계단

 

(1)번 경우에는 DP[1] + arr[3]이 될 것이고

(2)번 경우에는 arr[2] + arr[3]이 될 것이다. DP[2]에는 arr[1] + arr[2]가 들어가있다.

 

(1)번 경우는 점화식을 DP[i-2] + arr[i]로 세울 수 있지만

(2)번 경우는 arr[i-1] + arr[i]로 세운다면 그동안 누적된 점수가 포함되어 있지 않다. 계단은 1칸 또는 2칸을 오를 수 있으므로 i-2 계단을 밟지 않았다면 i-3 계단은 밟아야하므로 DP[i-3]을 더해주어야 한다.

 

 

소스 코드

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

int arr[301] = { 0, }, DP[301];

int main() {
	int n;
	cin >> n;

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

	DP[1] = arr[1];
	DP[2] = arr[1] + arr[2];

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

	cout << DP[n];
}