백준 - 2579 계단 오르기
본 문제의 요구사항은 아래와 같다.
주어진 계단이 있고 각 계단별로 점수가 있다.
계단을 오르는 규칙은 다음과 같다
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다.
2. 연속된 3개의 계단을 밟아서는 안된다.
3. 마지막 도착 계단은 반드시 밟아야 한다.
이러한 규칙들을 준수하면서 밟을수 있는 경우의 수를 따져서 가장 높은 점수를 출력해야 한다.
본문제를 풀기위해서 완전 탐색을 이용할수 없다. 완전탐색은 일반적으로 시간복잡도가 O(2^N) 이고 계단이 최대 300 개이므로 시간초과가 발생한다.
따라서 DFS 와 메모제이션 기법으로 중복 계산을 없애 계산 시간을 단축할 수 있다.
맨 마지막 계단을 반드시 밟아야 하기 때문에 출발은 제일 마지막 계단부터 내려오면서 합을 구한다.
함수 F(Ni) 를 i ~ 0 계단 까지의 밟을수 있는 최대 점수이고 V(Ni) 를 그 계단의 점수라고 한다면 라고 한다면 F(Ni) = MAX( F(Ni-1), F(Ni-2)) + V(Ni) 로 정의할수 있고 이를 dfs 함수로 구현할수 있다. 만약 i 번째 계단을 밟기 전에 i+1 번째 계단을 밟았다면 다음 i-1 로는 이동할수 없으므로 F(Ni) =F(Ni-2) + V(Ni) 로 표현할 수있다.
아울러 현재위치와 다음계단을 밟을수 있는지 여부를 기반으로 메모제이션을 수행한다.
구현된 코드는 아래와 같다.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int process(int needToLeap, int th);
vector<vector<int>> memo(2, vector<int>(301, -1));
vector<int> data;
int size;
int main()
{
cin >> size;
data.resize(size, -1);
for (int i = 0; i < size; i++)
{
cin >> data[i];
}
int result = process(0, size - 1);
cout << result << endl;
}
int process(int needToLeap, int th)
{
if (th == 0) return data[th];
if (th < 0) return 0;
if (memo[needToLeap][th] != -1) return memo[needToLeap][th];
int result = 0;
if (needToLeap == 0)
{
result = max(process(1, th - 1), process(0, th - 2)) + data[th];
}
else
{
result = process(0, th - 2) + data[th];
}
memo[needToLeap][th] = result;
return result;
}
needToLeap 은 이미 두칸을 연속으로 이동하였기 때문에 반드시 다음칸은 두계단을 이동해야 한다는 의미이다.
현재 위치와 needToLeap 값을 기준으로 계산후 메모를 수행하고 재귀호출에 의해 동일 조건의 계산이 필요할때 메모한 값을 로드하면 중복 계산을 막을 수 있다.