BOJ 2156 포도주 시식

문제출처 : https://www.acmicpc.net/problem/2156

1. 문제요약

- 일렬로 놓인 포도주 시식

- 선택하면 무조건 먹고 제자리

  연속 3잔을 마실 순 없음

- 포도주의 양이 주어졌을 때, 마실 수 있는 최대량?

- 1 <= n <= 10,000

- 1 <= 포도주 량 <= 1,000

2. 접근방법

- 일단 먹는다 안먹는다 뿐이니 다 해본다고 하면 2^10000...

- 현재 잔을 안먹는다.

  현재 잔을 먹었을 때 연속 1잔이다.

  현재 잔을 먹었을 때 연속 2잔이다.

  로 구분할 수 있음

- 나올 수 있는 경우의 수는

n-2 번째 잔	n-1 번째 잔	n 번째 잔
O	X	X
X	O	X
O	O	X
	X	O
X	O	O

- d[0] : 현재 잔을 안마셨을 때 최대

  d[1] : 현재 잔을 마시면 연속 한잔 일때 최대

  d[2] : 현재 잔을 마시면 연속 두잔 일때 최대

- 현재 연속 0잔 d[0] = max(d[0], d[1], d[2])

  현재 연속 1잔 d[1] = d[0] + n번째 포도주 량

  현재 연속 2잔 d[2] = d[1] + n번째 포도주 량

3. 시간복잡도

- n

4. 회고

- d[10001][3] 으로 생각 했는데 그럴 필요가 없네

소스코드

#include<iostream>
using namespace std;

int n, a, temp, d[3];

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

int main(void){
	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> a;
		temp = max(d[0], max(d[1], d[2]));
		if (d[1]) d[2] = d[1] + a;
		d[1] = d[0] + a;
		d[0] = temp;
	}
	cout << max(d[0], max(d[1], d[2])) << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]