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

문제

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

 

문제 내용

계단을 오르면서 얻을 수 있는 점수의 최댓값을 구하는 문제이다.

난 dynamic programming으로 문제를 해결했다.

 

문제 풀이

계단을 오르는데에 규칙이 있다.

1번) 3개의 계단을 연속으로 밟지 못한다. => 연속해서 밟을 수 있는 계단은 2개뿐이다.

2번) 한 번에 한 계단 또는 두 계단을 오를 수 있다. => 한 칸은 건너뛸 수 있다.  

 

이 규칙들을 따지며 규칙을 찾아보도록 하겠다.

빨간색 사각형이 계단을 밟는 경우, 엑스표가 밟지 않는 경우이다.

나올 수 있는 경우의 수는 2가지이다.

내가 지금 밟으려 하는 계단의 숫자가 n이라면,
1) n-2번째 계단을 반드시 밟고, n번째 계단을 밟는 경우
2) n-3번째 계단을 반드시 밟고, n-1번째 계단을 밟고, n번째 계단을 밟는 경우

 

코드

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


int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int n;
	cin >> n;
	vector<int>arr(n);
	vector<int>dp(n, 0);
	for (int i = 0; i < n; i++) cin >> arr[i];
	
	//문제 해결
	dp[0] = arr[0];
	dp[1] = arr[0] + arr[1];
	dp[2] = max(arr[0] + arr[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 - 1] << '\n';
}

 

문제 코드 설명

arr과 dp에 값을 받을 때 0번 인덱스부터 받았기 때문에, 출력 시 n-1번째 인덱스의 값을 출력한다.