2156번 포도주 시식

문제링크 : www.acmicpc.net/problem/2156

2156번: 포도주 시식

---

---

<미리 고려할 점>

 

- 기본적으로 2579번(2021.03.24 - [Baekjoon Online Judge] - 2579번 계단오르기)과 유사

 

- 2579번과는 다르게 0번~N-1번까지 꼭 선택해야하는 잔은 없으므로 입력은 모두 3칸씩 밀려받아, 0번부터 같은 점화식으로 고려한다.

 

- 2579번과 같은 점 : 이전 두 잔을 선택했다면 현재 잔은 선택 불가, 잔의 합을 최대로 만들어야함.

  2579번과 다른 점 : 2579번이 한 칸만 건너뛸 수 있었다면, 2156번은 두 칸까지 건너뛸 수 있음.

                          (2156번을 세 칸이상 건너뛰려고 하면 중간에 한 칸 선택하고 가는게 이득이기에 두 칸까지)

 

 

 

 

<알고리즘>

 

1) i번째 포도주잔까지 고려했을 때 최대 양으로 만드는 배열 dq 생성(크기는 N+3이상이여야 함)

 

2) 입력배열 3번부터 고려하여(3칸 밀려서 받았으므로) 아래 경우 중 큰 값을 dq에 입력

    2-1) 경우의 수 1. 이전 잔을 마셨을 경우, dq[i] = dq[i-3]+wine[i-1]+wine[i]

    2-2) 경우의 수 2. 이전 잔을 마시지 않았을 경우, dq[i] = dq[i-2]+wine[i]

    (여기서 dq[i]는 i번째 잔까지 고려했을때 구할 수 있는 최대 포도주 양의 합)

 

3) 2번과는 별개로 두 잔을 연달아 마시지 않는 경우를 고려하여, dq[i]=dq[i]와 dq[i-1]중 큰 값

    (wine[i-1]을 마셨든 안 마셨든, dq[i-1]번째와 dq[i]를 비교하여 wine[i]를 마실지 안 마실지 결정)

 

4) 끝까지 마시지 못하고 중간에(0~N-1중에서) 멈출수도 있기에 dq[i]를 새로 입력할때마다 maximum값 파악

 

5) 최종 dq의 가장 큰 값인 maximum값 출력

 

 

 

 

 

 

메모리 : 2016KB    시간 : 4ms

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

int main() {
	int N = 0;
	cin >> N;
	
	int wine[10001] = { 0, };
	int a = 0;
	for (int i = 3; i < N+3; i++) {
		cin >> a;
		wine[i] = a;
	}
	
	int maximum = 0;
	int dq[10001] = { 0, };
	for (int i = 3; i < N+3; i++) {
		dq[i] = max(dq[i - 3] + wine[i - 1] + wine[i], dq[i - 2] + wine[i]);
		dq[i] = max(dq[i - 1], dq[i]);
		maximum = max(dq[i], maximum);
	}

	cout << maximum;
	return 0;
}