[백준 / BOJ] 2579번: 계단 오르기

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

2579번: 계단 오르기

 

 

---

 

코드

---

1. 재귀호출 사용

#include <cstdio>
#include <algorithm>
using namespace std;
int n, stair[301];
int res[301] = {};

int upstair(int num) {
	if (num == 2) return stair[1] + stair[2];
	if (num < 2) return stair[num];
	if(!res[num]) res[num] = max(upstair(num - 3) + stair[num - 1], upstair(num - 2)) + stair[num];
	return res[num];
}
int main() {
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) scanf("%d", &stair[i]);

	printf("%d", upstair(n));
	return 0;
}

 

 

2. 반복문 사용

#include <iostream>
#include <algorithm>
using namespace std;
int n, stair[301];
int res[301] = {};

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

	cin >> n;

	for (int i = 1; i <= n; i++) cin >> stair[i];

	res[1] = stair[1]; res[2] = stair[1] + stair[2];

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

	cout << res[n];
	return 0;
}

---

 

 

마지막 계단은 무조건 밟아야 하며, 3개의 계단을 연속해서 밟을 수 없다. i번째 계단을 밟는 방법에 대한 경우는 다음과 같이 나눌 수 있다.

1. i-3번째 계단을 밟고, i-1번째 계단과 i번째 계단을 밟는다. -> i번째 계단과 i-1번째 계단을 연속으로 밟았을 경우이며, i-2번째 계단은 밟을 수 없으므로 건너 뛰고 i-3번째 계단을 밟을 수 있다.
2. i-2번째 계단을 밟고, i번째 계단을 밟는다.

경우를 나누었으면, i번째 계단까지 밟았을 때, 점수가 최대가 되는 값인 dp[i]을 구한다. 

1. 첫번째 경우에 대해: 점수의 최댓값 dp[i] = (i-3번째 계단까지 밟았을 때 점수의 최대값) + (i-1번 계단의 점수) + (i번 계단의 점수) = dp[i-3] + stair[i-1] + stair[i]
2. 두번째 경우에 대해: 점수의 최댓값 dp[i] = (i-2번째 계단까지 밟았을 때 점수의 최댓값) + (i번 계단의 점수) = dp[i-2] + stair[i]

따라서 dp[i]는 dp[i-3] + stair[i-1] + stair[i] 와 dp[i-2] + stair[i] 중 더 큰 값을 취하면 된다.