백준 알고리즘 9456번 : 스티커

문제 소개

---

---

• 2 x n 크기의 스티커의 점수가 담긴 리스트가 주어지고 한 스티커를 선택하면 변을 공유하는 스티커(상하좌우 스티커)는 사용할 수 없다.

• 전형적인 DP(다이나믹 프로그래밍) 문제이다.

---

첫번째 접근

• 단순하게 생각했었다. 상하좌우스티커는 사용할 수 없으므로 대각선을 이용해서 선택하는 빨간색, 파란색 방식 두가지를 비교해서 큰 값을 선택하는 방법

• 하지만 위 스티커 배열에서 최대 값은 [50,50,100,60] 으로 sum = 260 이 되기 때문에 본 방법은 안된다.
  -> DP로 가야한다.

---

두번째 접근

• DP 접근방식
• DP문제는 항상 기존값과 비교하며 더 큰 값을 선택해야 한다.

dp = max(기존값,현재값)

• 2번째 열 (index가 1)은 항상

  arr[0][1]+= arr[1][0]
  arr[1][1]+= arr[0][0]

으로 선택이 되고 이후에 열은 3번째열(index가 2)인 열을 예를 들자면

arr[0][2] += max(arr[1][1],arr[1][0])
arr[1][2] += max(arr[0][1],arr[0][0])

이 되게 된다.

이것을 일반항으로 나타내게 되면

if(i >= 2)
arr[0][i] += max(arr[1][i-1],arr[1][i-2])
arr[1][i] += max(arr[0][i-1],arr[0][i-2])

로 나타낼 수 있다.

---

전체 정답 코드

n = int(input())
ans = []
for _ in range(n):
  k = int(input())
  arr = []
  for _ in range(2):
    arr.append(list(map(int,input().split())))
  if len(arr[0]) == 1:
    ans.append(max(arr[0][0],arr[1][0]))
  else:
    arr[0][1] += arr[1][0]
    arr[1][1] += arr[0][0]
    for i in range(2,k):
      arr[0][i] += max(arr[1][i-1],arr[1][i-2])
      arr[1][i] += max(arr[0][i-1],arr[0][i-2])
    ans.append(max(arr[0][k-1],arr[1][k-1]))

for j in ans:
  print(j)