[BOJ] 백준 2156 포도주 시식 (Swift)

문제

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

2156번: 포도주 시식

풀이

계단 오르기 문제와 비슷한 문제였습니다.

하지만 계단 오르기와 다르게, 마지막 포도주를 꼭 먹어야 하지는 않습니다.
[1, 99, 100, 2] 와 같은 경우 99와 100을 먹는게 가장 큰 값입니다. 마지막 2를 먹을 필요가 없습니다.

[100, 99, 1, 2, 100, 1] 로 포도주가 나열되어 있다고 가정합시다.

첫번째 포도주 까지 있다면, 첫번째 포도주를 마셔야 무조건 가장 많이 마실 수 있습니다.
두번째 포도주 까지 있다면, 첫번째 포도주와 두번째 포도주를 마셔야 무조건 가장 많이 마실 수 있습니다.

세번째 포도주 까지 있다면?
첫번째 + 세번째, 두번째 + 세번째, 첫번째 + 두번째로 나뉠 것입니다.
첫번째 + 두번쨰가 가장 많은 포도주를 마실 수 있겠네요.

n번째 포도주 까지 있다면?

1. n - 3 까지 마신 포도주의 최대 값 + n - 1 포도주 + n 포도주
2. n - 2 까지 마신 포도주의 최대 값 + n 포도주
3. n - 1 까지 마신 포도주의 최대 값 

으로 나눌 수 있습니다.

정의 : $f(n)$ = n번째 포도주까지 마실 수 있는 최대양
초기값 : $f(1) = array(1), f(2) = array(1) + array(2)$
점화식 : $f(n) = max(f(n - 3) + array(n - 1) + array(n), f(n - 2) + array(n),f(n-1))$

소스코드

후기

계단 오르기 문제와 비슷했지만,
마지막 포도주를 꼭 마셔야 할 필요가 없어서 조건이 하나 추가되었던 문제였습니다.

[100, 99, 1] 과 같은 예외 테스트를 확인해서 조건을 떠올릴 수 있었습니다.