백준 9465 - 스티커 파이썬

문제 

9465번: 스티커

 

아이디어(구현은 안하고 우선 생각만 해봄) 

- 약간 그리디 스타일 

제일 큰거 고르고 

위, 아래, 왼쪽, 오른쪽 값 삭제 

그리고 남은 것들 중 제일큰거 고르고 

똑같이 위, 아래, 왼쪽, 오른쪽 값 삭제해서 

모든 원소가 사라지면 멈추는 함수를 만든다 

- 누적값을 메모하면서 탐색하기 

대각선 값을 경우의 수로 두고 메모하면서 탐색하기

- bfs로 풀기 

 

해결코드 

t = int(input())
for i in range(t):
  s = []
  n = int(input())
  for k in range(2):
    s.append(list(map(int, input().split())))
  for j in range(1, n):
    if j == 1:
      s[0][j] += s[1][j - 1]
      s[1][j] += s[0][j - 1]
    else:
      s[0][j] += max(s[1][j - 1], s[1][j - 2])
      s[1][j] += max(s[0][j - 1], s[0][j - 2])
  print(max(s[0][n - 1], s[1][n - 1]))

누적값을 메모하면서 풀이하는 방식으로 진행했다