< 백준 BaekJoon : 2156번 포도주 시식 > C++

<< 문제 >> 

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

이전에도 비슷한 문제인 계단 오르기 문제가 있었다. 

 

별 생각 없이 같은 방법으로 풀면 되겠지 했는데, 생각치 못했던 것이 포도주를 안먹는 경우였다.

 

이전 계단 오르기 문제에서는 무조건 오르는 것이 이득이여서 선택하는 경우만 있었는데,

 

이 문제는 오히려 포도주를 계속 안먹는게 이득인 상황이 있어서 조금 곤란했다.

 

 

<< 코드 >>

#include <iostream>
using namespace std;

// (i-1을 마실 떄, i-2를 마실 때)
long long arr[10001][2];

int main() {

	int num;
	cin >> num;

	
	int temp;
	if (num == 1) {
		cin >> temp;
		cout << temp;
		return 0;
	}

	for (int i = 1; i < num + 1; i++) {
		cin >> temp;
		arr[i][0] = temp;
		arr[i][1] = temp;
	}
	
	long long maxValue = -1;

	long long lastMax;
	for (int i = 2; i < num + 1; i++) {
		// i번째를 먹는 경우
		if (arr[i][0] == 0) {
			temp = max(arr[i-1][0], arr[i-1][1]);
			arr[i][0] = temp;
			arr[i][1] = temp;
		}
		else {
			arr[i][0] += arr[i - 1][1];
			arr[i][1] += max(arr[i - 2][0], arr[i - 2][1]);
		}

		// 안먹는 경우를 고려
		lastMax = max(arr[i - 1][0], arr[i - 1][1]);
		arr[i][0] = max(arr[i][0], lastMax);
		arr[i][1] = max(arr[i][1], lastMax);

		// 최대값 찾기
		if (arr[i][0] > maxValue) {
			maxValue = arr[i][0];
		}
		if (arr[i][1] > maxValue) {
			maxValue = arr[i][1];
		}
	}

	cout << maxValue;
}

 

 

 

<< 깃헙 >>

https://github.com/J2on/StudyAlgorithm_Part2/tree/main/%EB%B0%B1%EC%A4%80/Silver/2156.%E2%80%85%ED%8F%AC%EB%8F%84%EC%A3%BC%E2%80%85%EC%8B%9C%EC%8B%9D