[BAEKJOON] 2156번 포도주 시식

문 제

 

소 스  코 드

#include<iostream>
#include<algorithm>

int main() {

	int N;
	std::cin >> N;

	int *wine{ new int[N] };

	for (int i = 0; i < N; ++i) std::cin >> wine[i];

	int *temp{ new int[N] };
	temp[0] = wine[0];
	temp[1] = wine[0] + wine[1];
	temp[2] = std::max({ wine[1] + wine[2], wine[0] + wine[2], wine[0] + wine[1]});
	

	for (int i = 3; i < N; ++i) {
		temp[i] = std::max(temp[i - 2] + wine[i], temp[i - 3] + wine[i - 1] + wine[i]);
		temp[i] = std::max(temp[i - 1], temp[i]);
	}

	std::cout << temp[N - 1];
	
	delete[] wine;
	delete[] temp;


	return 0;
}

 

풀 이

 

[백준] 계단 오르기 : https://studycl.tistory.com/33?category=1131353

 

• 계단 오르기 문제와 다른 점은 마지막 계단을 밟지 않아도 된다는 점이다.
  
  

• 6개의 포도잔 ( 6, 10, 13, 9, 8, 1) 이 있을 경우

  첫 번째의 경우 1번 포도주를 먹는 경우인 : 6

  두 번째의 경우 1번 2번 포도주를 먹는 경우 : 16

  세 번째의 경우 2번 3번 포도주를 먹는 경우 : 23

  네 번째의 경우 1번 3번 4번 포도주를 먹는 경우 : 28

  다섯 번째의 경우 1번 2번 4번 5번 포도주를 먹는 경우 : 33

  여섯 번째의 경우 2번 3번 5번 6번 포도주를 먹는 경우 : 32 

  위의 경우를 보면 볼 수 있지만, 다섯 번째의 경우가 여섯 번째의 경우보다 큰 것을 알 수 있다.

  이는 마지막 포도주를 무조건 안먹어도 되는 경우가 있기 때문에 이전에 있는 누적값과 비교하여

  더 높은 누적치로 바꿔서 정립해야 한다.

 

결 과 값

 

 

문 제  출 처

문제 링크 : [ BAEKJOON ] : https://www.acmicpc.net/problem/2156