🔥

문제

용돈을 다쓴 윌리는 돈을 벌기 위해 N일동안 부모님의 가게를 도우려고 한다.


윌리가 일하는 가게에서는 설거지하기, 요리하기, 마당쓸기 세 가지의 일이 있다.


윌리는 지루한 일을 굉장히 싫어하기 때문에, 이틀연속 같은 일을 하는 것은 불가능하다.


i일에 설거지하기, 요리하기, 마당쓸기에 대한 용돈이 주어질 때, 벌 수 있는 돈의 최대를 구하자.

입력

첫째 줄에 윌리가 일하는 날 N이 주어진다. (1 ≤ N ≤ 10^5)


둘째 줄부터 N개의 줄에 설거지, 요리, 마당쓸기를 할때의 용돈 xi, yi, zi들이 주어진다. (1 ≤ xi, yi, zi ≤ 10^4)

출력

첫째 줄에 윌리가 받을 수 있는 용돈의 최대값을 출력한다.

예제 1 입력

3
10 40 70
20 50 80
30 60 90

예제 1 출력

210

예제 2 입력

1
100 10 1

예제 2 출력

100

Source

n = int(input())
dp = [[0 for _ in range(3)] for _ in range(n + 1)]

for i in range(1, n + 1):
	x, y, z = map(int, input().split())

	dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + x
	dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + y
	dp[i][2] = max(dp[i - 1][0], dp[i - 1][1]) + z

print(max(dp[n][0], dp[n][1], dp[n][2]))

참고