1. 문제

2156번

2. 코드

• 파이썬에서는 C언어와 같이 변수나 변수 공간을 미리 정의 하지 않고 동적으로 할당해준다.
• 편하긴 하지만 index 문제 등이 발생할 수 있으므로 미리 선언하는 습관을 들이자!

# 메모이제이션 공간 dp와 숫자를 입력받을 공간 num_을 미리 정의 했다.
# 초기값 설정 시 index 에러 문제가 많은데 이렇게 미리 공간을 설정해주면 그런 문제가 덜 하다.
num_ = [0 for _ in range(99999)]
dp = [0 for _ in range(999999)]

N = int(input())
for i in range(N):
    num_[i] = int(input())
    
dp[0] = num_[0]
dp[1] = num_[0] + num_[1]

'''
dp[2]는 3개의 숫자 중 3연속이 되지 않도록 고르는 문제이므로,
3개 중 2개를 뽑는 총 3가지 경우의 수가 있다.

3가지 경우의 수 중 합이 최대가 되는 case를 바인딩 한다.
 - max() 메서드 이용
'''
dp[2] = max(
    (num_[0] + num_[1]),
    (num_[0] + num_[2]),
    (num_[1] + num_[2])
)

# dp[n]의 경우의 수는 총 3가지가 있다.
for n in range(3, N):
	# 첫번째, 맨 뒤의 2개 수를 연속으로 선택 : n-2번째 숫자는 제외 되어야 함
    a = dp[n-3] + num_[n-1] + num_[n]
    # 두번째, n번째 숫자를 선택하고 n-1번째 숫자를 선택하지 않을 때
    b = dp[n-2] + num_[n]
    # 세번째, n번째 숫자를 선택하지 않을 때 : 사실상, dp[n-1]과 동일하다.
    c = dp[n-1]
	
    # 세가지 경우의 수 중에서 최댓값을 바인딩 한다.
    dp[n] = max(a, b, c)

print(max(dp))