백준 2579번: 계단 오르기

[문제 링크]

2579번: 계단 오르기

---

TopDown 으로 푸는 경우 위에 계단을 밟았는지 안밟았는지 여부에 따라 다른 점화식으로 동작하도록 하였고, 위에 계단을 밟은 경우와 안밟은 경우의 최댓값을 다르게 저장하기 위해 2차원 배열로 메모이제이션 하였다.

기저사례로 현재 위치가 계단 범위를 벗어날 경우 값이 없으므로 0을 반환해주었다.

 

BottomUp 으로 푸는 경우 마찬가지로 아래 계단을 밟았을 경우와 안밟았을 경우의 값이 다르기 때문에 2차원 배열로 메모이제이션 하였다. 첫번째 계단과 두번째 계단을 미리 계산하여 결과값을 메모이제이션한 다음, 미리 계산한 값을 이용하여 세번째 계단부터 N번째 계단까지 계산하는 형태로 구현하였다.

---

#include <iostream>
#include <cstring>
using namespace std;

int N, stairs[301], memoTop[301][2], memoBot[301][2];

inline int max(int a, int b) { return a > b ? a : b; }

int TopDown(int here, int check)
{
	// check == 0 : 위에 계단 밟은 경우
	// check == 1 : 밟지 않은 경우
	if (here < 0) return 0; // 기저사례: 계단을 벗어났을 경우 0 반환

	int& ret = memoTop[here][check];
	if (ret != 0) return ret;

	if (check)
		ret = max(TopDown(here - 1, 0) + stairs[here], TopDown(here - 2, 1) + stairs[here]);
	else
		ret = TopDown(here - 2, 1) + stairs[here];

	return ret;
}

int BottomUp(int N)
{
	// memoBot[i][0] : 아래 계단 밟은 경우
	// memoBot[i][1] : 밟지 않은 경우
	memoBot[0][0] = memoBot[0][1] = stairs[0];
	memoBot[1][1] = stairs[1];
	memoBot[1][0] = stairs[0] + stairs[1];
    
	for (int i = 2; i < N; i++)
	{
		memoBot[i][1] = max(memoBot[i - 2][0], memoBot[i - 2][1]) + stairs[i];
		memoBot[i][0] = memoBot[i - 1][1] + stairs[i];
	}
    
	return max(memoBot[N - 1][0], memoBot[N - 1][1]);
}

int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
		cin >> stairs[i];

	// Top-Down
	cout << TopDown(N-1, 1) << endl;
    
	// Bottom-Up
	cout << BottomUp(N) << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 64 day