9465번 파이썬

처음에 이 문제를 풀을 때 뜯을려고 하는 스티커의 왼쪽 부분을 전부 다 검사해서(인접 변 제외) max인 값을 현재 스티커 값과 더해서 dp를 만들려고 했는데 답은 잘 나오는데 시간 초과 에러가 떴다..아마 시간 복잡도가 n^2이라 그런것 같다.

그래서 생각한 다른 방법은 만약 첫번째 행의 3번째 스티커를 뜯었다고 가정할때 (보기에선 100값 스티커) 두번째 행의 2번째와 첫번째 dp값 중 최대값만 계산해서 현재 스티커 값에 플러스 해주는 방식이다. 이걸 코드로 나타내면 아래와 같고 이런 방식을 이용하는 이유는 현재 스티커 값을 최대로 뜯을려고 하기 때문에 이웃한 변 다음칸을 뜯는게 효율적이지만 값이 그 옆에꺼가 더 클 경우가 그게 더 효율적일 수 있기 때문이다.

그리고 현재 col-3한 값을 구하는 것은 col-1을 구하는 경우에 포함되어있다.

import sys
input = sys.stdin.readline
t = int(input())
for __ in range(t):
  n = int(input())
  ary = [list(map(int,input().split())) for _ in range(2)]
  if n >=2:
    ary[0][1] +=ary[1][0]
    ary[1][1] += ary[0][0]
  for col in range(2,n):
    for row in range(2):
      ary[row][col]+=max(ary[(row+1)%2][col-1],ary[(row+1)%2][col-2])
  print(max(ary[0][n-1],ary[1][n-1]))