실1
해당 문제는 dp의 바텀업 방식으로 풀어내는 문제이다.
난이도가 올라갈수록 바텀업을 잘 풀어낼 수 있어야 될 것 같은 직감이 든다.
바텀업 방식은 점화식을 만들어서 풀어야 한다고 하는데, 꼭 점화식을 만들 수 있어야 하지는 않다.
n을 1부터 하나씩 증가시켜가면서 규칙성을 찾기만하면 그걸 코드로 구현해낼 수 있다.
먼저 n이 1일 경우를 생각해본다. 최대값은 첫번째 잔만 선택하므로 6이다.
n이 2일 경우 최대값은 첫번째 잔 두번째 잔을 더해서 16이다.
n이 3일 경우 (첫번째 잔, 세번째 잔), (첫번째 잔, 두번째 잔), (두번째 잔, 세번째 잔) 조합중 최대값을 선택한다.
여기까지만 봐도 대충 3개 중 최대값을 구하게 되겠다고 느낌이 오면 좋다. 안와도 된다.
n이 4일 경우 (네번째 잔, 세번째 잔, 첫번째 잔(까지의 최대값)), (네번째 잔, 두번째 잔까지의 최대값), (세번째 잔까지의 최대값) 중 최대값을 구해야 한다.
이 규칙은 n이 커져도 똑같다.
해당 내용을 코드로 구현하면
ans[i] = max(arr[i] + arr[i-1] + ans[i-3], ans[i-1], arr[i] + ans[i-2])
n번째 값마다 최대값이 들어가는 리스트를 만들고, 이 리스트를 이용해 커지는 n 값을 계속 구해 나간다.
n = int(input())
arr = [0]
for _ in range(n):
arr.append(int(input()))
ans = [0] * (n+1)
def solution():
ans[1] = arr[1]
if n > 1:
ans[2] = arr[2] + arr[1]
if n > 2:
for i in range(3, n+1):
ans[i] = max(arr[i] + arr[i-1] + ans[i-3], ans[i-1], arr[i] + ans[i-2])
print(max(ans))
solution()