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

풀이 1

N is length of glasses.
time complexity: O(N)
space complexity: O(2N)

• 지금 경우의 수 포함하면
• (검은색) 0번 연속 -> ans[i-1]이 걱정될 수 있다. 그러나 그 경우에서는 현재의 자신을 선택하지 않기 때문에 무엇이든 괜찮다.
  • ans[i] = ans[i-1]
• (파란색) 1번 연속 -> glasses[i]는 무조건 포함고, i-2는 포함시켜서 의도적으로 1번 연속을 만든다.
  • ans[i] = glasses[i] + ans[i-2]
• (빨간색) 2번 연속 -> glasses [i] + glasses[i-1]을 넣어서 의도적으로 2번 연속을 만든다.
  • ans[i] = glasses[i] + glasses[i-1] + ans[i-3]

n = int(input())
glasses = [0] + [int(input()) for _ in range(n)]
answer = [0] * (n+1)

answer[1] = glasses[1]
if n >= 2:
    answer[2] = answer[1]+glasses[2]

for i in range(3,n+1):
    answer[i] = answer[i-1] # 이번 것 포함 0번 연속일 때
    answer[i] = max(answer[i],answer[i-2]+glasses[i])
    answer[i] = max(answer[i],answer[i-3]+glasses[i-1]+glasses[i])

print(max(answer))

space complexity 최적화

중요한 것은 a, b,c가 의미하는 지 아는 것이다.
주의해야 할 점은 a,b,c의 의미는 ans[i-1], ans[i-2], ans[i-3]을 의미하지 않는다.

• t+a에서 a 는 answer[i-2] 이다. 즉 answer[i-2]+glasses[i]
• t+b에서 b는 ans[i-3]+glasses[i-1] 이다. 즉 ans[i-3]+glasses[i-1]+ glass[i]

원라인으로 썼기 때문에 a는 b의 값을 연산할 때 값이 바뀌지 않는다.

a, b, c = 0, 0, 0
for i in range(1,int(input())+1):
    t = int(input())
    a, b, c = max(a,b,c), t+a, t+b
print(max(a,b,c))