https://www.acmicpc.net/problem/2156
알고리즘 공부를 3달만에 해서 그런지 조금만 생각하면 풀 수있는 dp문제도 애를먹었다.
dp라는 배열을 생성하고 이 배열엔 x번째의 인덱스에 0부터 x번째의 마신다/마시지 않는다의 선택지를 골라가며 선택한 가장 큰 값이 저장되어있다.
그럼 x번째에는 어떻게 가장 큰 값이 들어갈까.
dp[x]에 가장 큰 값이 들어가기 위해선 세개의 선택지가 존재한다.
- 현재 포도주(x번째)의 마시고, 직전(x-1)을 마신다.
- 현재 포도주를 마시고, 직전의 것은 건너 뛴다.
- 현재 포도주를 마시지 않는다.
현재 arr[x]가 8이라 가정했을 때,
1번 선택지의 경우 다음과 같다.
하지만 여기서 생각해야할 것이,
현재 포도주와 직전의 포도주를 마신다는 것은 전전의 포도주를 안마신다는 것이다.
즉, x-3번째의 포도주의 합까지 생각해주어야 1번 선택지가 완벽해지는 것이다.
그러므로 1번 선택지의 경우 위와 같이 선택할 수 있다.
2번의 경우는 더욱 간단하다.
직전의 것을 마시지 않는 다는 것은, 전전의 포도주와 현재의 포도주만 선택하면 된다.
즉, 다음과 같다.
3번의 경우는 더더욱 간단하다.
현재의 포도주를 마시지 않는다는 것은 바로 직전까지의 포도주의 합을 1번과 2번과 비교해주면 된다.
즉, 다음과 같다.
이를 코드로 나타내면 다음과 같다.
for i in range(3, n):
dp[i] = max(dp[i-1], dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i])
# 현재를 마시지 않을 때,
# 전전꺼를 안마시고 현재와 전꺼를 마셨을 때,
# 전꺼를 안마셨을 때,
# 전체 코드
n = int(input())
arr = []
for _ in range(n):
arr.append(int(input()))
dp = [0] * 10000
dp[0] = arr[0]
if n > 1:
dp[1] = arr[1] + arr[0]
if n > 2:
dp[2] = max(arr[2] + arr[1], arr[2] + arr[0], dp[1])
for i in range(3, n):
dp[i] = max(dp[i-1], dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i])
# 현재를 마시지 않을 때,
# 전전꺼를 안마시고 현재와 전꺼를 마셨을 때,
# 전꺼를 안마셨을 때,
print(dp[n-1])