[삼성 알고리즘] Dynamic Programming(계단오르기)

안녕하세요 이번 포스팅은 동적프로그래밍 백준 계단오르기 문제입니다.

 

1. 문제 이해

해당 문제는 연속으로 3칸을 이동할 수 없으며 처음 첫 번째 혹은 두 번째 칸으로 시작을 진행해야하고 마지막 칸을 반드시 밟아야 하는 3가지 조건이 존재합니다.

 

-- 조건

a. 연속된 3칸을 밟을 수 없음.

b. 첫 번째 칸 혹은 두 번째 칸을 시작 칸으로 설정해야 함.

c. 마지막 칸을 반드시 밟아야 함. 

 

 

2. 식 만들기

위 식을 만드는 방법은 간단합니다. 결국 n번째 계단을 오르기 위해서는 n-1번째 까지의 상황들을 고려해서 여기에 n번째라는 경우의 수가 추가된 것을 고려하면 됩니다

 

예를 들어 n번째 까지의 최댓값을 구하는 경우 n번째 칸은 무조건 밟아야 하기 때문에

answer(n) = max(answer(n-2) + a(n) , answer(n-3) + a(n-1) + a(n))

의 값으로 구할 수 있습니다. 즉 N번째를 무조건 밟기 때문에 N-1번째 혹은 N-2번째를 밟지 말아야 하며 해당 조건을 만족한 answer(n)은 위 점화식이 성립하게 됩니다.

 

하지만 위의 식은 1 <= n <= 3까지의 경우 성립이 되지 않습니다.

때문에 해당 부분에 대해서는 예외적으로 직접 값을 따로 설정해주는 것이 점화식을 만드는데 더 어려움없이 만들 수 있습니다.

answer(1) = a(1)

answer(2) = max(a(1)+a(2), a(2))

answer(3) = max(a(1)+a(3), a(1)+a(2))

결과적으로 위와 같이 의 값을 얻을 수 있습니다.

 

3. 소스 코드

#include<iostream>
#include<algorithm>

using namespace std;
int arr[301];
int maxs[301];

int make_maximum(int a,int b,int c,int i) {
if (a >= b && a >= c) {
return a;
}
else if (b >= a && b >= c) {
return b;
}
else if (c >= a && c >= b) {
return c;
}
}

int main(void) {
int N,buf;
cin >> N;
for (int i = 1; i <= N; i++) {
cin >> buf;
arr[i] = buf;
maxs[i] == -1;
}
maxs[0] = 0;
maxs[1] = arr[1];
maxs[2] = max(arr[1] + arr[2], arr[2]);
maxs[3] = max(arr[1] + arr[3], arr[2] + arr[3]);
for (int i = 4; i <= N; i++) {
maxs[i] = max(maxs[i - 2] + arr[i], maxs[i - 3] + arr[i] + arr[i - 1]);
}
cout << maxs[N] << endl;
return 0;
}