백준 2156번: 포도주 시식

[문제 링크]

2156번: 포도주 시식

---

https://onlytrying.tistory.com/74 

계단 오르기와 유사한 형태의 문제였다.

 

차이점은 계단 오르기 문제는 마지막 계단을 반드시 밟아야 한다는 조건이 있었지만,

이 문제는 마지막 포도주를 반드시 마셔야 한다는 조건이 없다는 것이다.

따라서 마지막 포도주를 반드시 마시는 경우와 마시지 않는 경우의 최대값을 추가로 비교해줘야 원하는 결과를 얻을 수 있다.

---

#include <iostream>
using namespace std;

int wine[10001], memo[10001][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;

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

	if (check)
		ret = TopDown(here - 1, 0) + wine[here];

	return ret = max(ret, max(TopDown(here - 1, 1), TopDown(here - 2, 1) + wine[here]));
}

int BottomUp(int n)
{
	// memo[i][0] : 앞에 포도주 마셨을 때
	// memo[i][1] : 앞에 포도주 안 마셨을 때

	memo[0][0] = memo[0][1] = wine[0];
	memo[1][0] = wine[0] + wine[1];
	memo[1][1] = wine[1];

	for (int i = 2; i < n; i++)
	{
		memo[i][0] = max(memo[i - 1][1] + wine[i], memo[i - 1][0]);
		memo[i][1] = max(memo[i - 2][0] + wine[i], memo[i - 2][1] + wine[i]);
	}

	return max(memo[n - 1][0], memo[n - 1][1]);
}

int main(void)
{
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> wine[i];

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

	return 0;
}

 

 

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