문제 : https://www.acmicpc.net/problem/9465
주 발상
- greedy로 푸는 것이다.
- ans[j][i]는 i의 길이의 스티커에서 j번째 상황에서 낼 수 있는 가장 큰 값을 저장해 놓는다.
def solved(d, n):
ans = [[0]*(n+1) for _ in range(3)]
for i in range(1, n+1):
ans[0][i] = max(ans[0][i-1], ans[1][i-1], ans[2][i-1])
ans[1][i] = max(ans[0][i-1], ans[2][i-1]) + d[0][i-1]
# 아래쪽을 뜯었으니(xo) ans[0][i-1], ans[2][i-1]
# 즉 xx or ox중 하나의 경우의 수를 선택 해야한다.
# 그래서 그 중 큰거 더하고 !
# d[0][i-1]은 아래를 뜯었으니 그 스티커의 값을 넣는 것이다.
ans[2][i] = max(ans[0][i-1], ans[1][i-1]) + d[1][i-1]
print(max(ans[0][n], ans[1][n], ans[2][n]))
for i in range(int(input()), 0, -1):
solved([list(map(int, input().split())) for i in range(2)], int(input()))
ans는 i번째 줄의 스티커를 뜯을 때, 각각의 경우에 따른 최대값을 나타낸다.
ans[0][i]는 스티커가
x
x
하나두 안뜯긴 것
ans[1][i]는 스티커가
o
x
위만 뜯긴 것
ans[i][1]는 스티커가
x
o
아래만 뜯긴 것