[백준 9465번] 스티커 - python

문제 링크

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

9465번: 스티커

풀이

- dp 문제

- 점화식 이해하기 어려웠음 

1. 1번 인덱스의 경우

아래 같은 색깔의 칸끼리 더한 경우 최댓값. 즉 왼쪽 대각선 아래나 왼쪽 대각선 위쪽의 값과 자기 자신을 더한 값이 최댓값 

data[0][i] += data[1][0]
data[1][i] += data[0][0]

2. 2번 이상 인덱스의 경우 

위 아래 왼쪽 오른쪽의 스티커는 사용할 수 없으므로, 

빨간색 위치의 경우 왼쪽 대각선 아래값과 왼쪽 대각선 아래의 왼쪽값 중의 최댓값과 자기 자신을 더한 값이 최댓값

파란색 위치의 경우 왼쪽 대각선 위값과 왼쪽 대각선 위쪽의 왼쪽값 중의 최댓값과 자기 자신을 더한 값이 최댓값 

data[0][i] += max(data[1][i-1], data[1][i-2])
data[1][i] += max(data[0][i-1], data[0][i-2])

3. 출력은 n-1 인덱스의 위와 아래값 중 최댓값 

print(max(data[0][n-1], data[1][n-1]))

 

4. 전체 코드 

t = int(input())

for _ in range(t):
  n = int(input())

  data = []
  for _ in range(2):
    data.append(list(map(int,input().split())))

  for i in range(1,n):
    if i == 1 :
      data[0][i] += data[1][0]
      data[1][i] += data[0][0]
    else:
      data[0][i] += max(data[1][i-1], data[1][i-2])
      data[1][i] += max(data[0][i-1], data[0][i-2])

  print(max(data[0][n-1], data[1][n-1]))