문제
풀이
문제의 포인트는
- 계단을 1칸씩 또는 한 칸 뛰어서 오를 수 있다.
- 계단을 3칸 연속으로 오르면 안된다.
- 계단마다 점수가 있다.
- 마지막 계단에 반드시 도착해야 한다.
- 마지막 계단에 도착할 때까지 지나올 수 있는 계단의 최대 값을 구한다.
반복문과 재귀함수 2가지 방법을 사용하여 코드를 작성해봤습니다.
반복문 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <algorithm>
#include <vector>
#include <iostream>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int n;
cin >> n;
vector<int> steps(n + 1);
vector<vector<int>> cache(n + 1, vector<int>(2, 0));
for (int i = 1; i < n + 1; i++)
cin >> steps[i];
cache[1][0] = cache[1][1] = steps[1];
for (int i = 2; i < n + 1; i++)
{
// 두칸 점프해서 현재 계단 i로 온 경우
cache[i][0] = max(cache[i - 2][0], cache[i - 2][1]) + steps[i];
// 한칸 점프해서 현재 계단 i로 온 경우
// 이 경우에는 바로 전 칸의 두 칸 점프한 경우만 가능
cache[i][1] = cache[i - 1][0] + steps[i];
}
int res = max(cache[n][0], cache[n][1]);
cout << res;
return 0;
}
재귀함수 사용
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int steps[301];
int cache[301][2];
int n;
int getMaxScore(int L, int isContinuos)
{
int &ret = cache[L][isContinuos];
// 기저 사례
if (L < 0)
return 0;
if (L == 0)
return steps[0];
// 이미 구했으면 바로 return
if (ret != -1)
return ret;
// 현재 계단이 2개 붙어있는 경우
// 전 칸의 계단은 검사하지 않는다.
if (isContinuos == 1)
return cache[L][isContinuos] = steps[L] + getMaxScore(L - 2, 0);
// 현재 계단이 다른 계단과 붙어있지 않은 경우
// 바로 전의 계단과 2칸 전의 계단을 모두 검사
else
return cache[L][isContinuos] = steps[L] + max(getMaxScore(L - 1, 1), getMaxScore(L - 2, 0));
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
cin >> steps[i];
memset(cache, -1, sizeof(cache));
cout << getMaxScore(n - 1, 0);
return 0;
}
