[Beakjoon] #9465 - 스티커

풀 때도 이해가 안갔지만 풀이를 보고도 애매한 문제 .. ㅎㅎ

우선 스티커의 위치와 값을 배열로 만들면 다음과 같다.

index	0	1	2	3	4
0	50	10	100	20	40
1	30	50	70	10	60

이제 조건을 생각해보자
어떤 자리를 하나 선택하면 그 자리의 상, 하, 좌, 우는 더 이상 쓸 수 없는 스티커가 된다.
예를 들어 50을 선택한다고 하면 양옆의 그 양옆인 10, 30은 더 이상 사용할 수 없게된다.

index	0	1	2	3	4
0	50	10 + 30 = 40	max(100, 30) + 100 = 200	max(120, 100) + 20 = 140	max(210, 120) + 40 = 250
1	30	50 + 50 = 100	max(40, 50) + 70 = 120	max(200, 40) + 10 = 210	max(140, 200) + 60 = 260

조건을 고려하여 가능한 최대값을 구하는 표는 다음과 같다.

우선 첫번째 등장하는 50을 사용한다고 해보자 10과 30은 더 이상 사용할 수 없다.
그리고 50에 50을 더한 값인 100을 저장한다.

이번에는 앞서 사용한다고 했던 50을 사용하지 않고 30을 사용한다고 해보자.
이번에는 50과 50은 더 이상 사용할 수 없게된다.
그리고 10에 30을 더한 값인 40을 저장한다.

이제 dp[0][2]에 쓸 수 있는 값은 2가지이다.
우선 dp[0][2] 자리의 스티커를 사용한다고 하면 dp[0][1]의 값은 고려 대상이 아니다.
따라서 30과 100 중에 더 큰 값을 골라 채워준다.

이제 3열을 보자. 바로 앞에서 dp[0][2]을 사용한다고 했으므로 dp[1][3] 스티커를 사용해야 한다.
그렇다면 여기서도 두가지의 상황을 고려해볼 수 있다.
1. 앞서 계산한 값인 dp[0][2] 값을 사용하기
2. 처음 상황에서 30을 사용했다는 가정하에 40을 사용하기 (40을 사용하면 dp[0][2] 자리의 값은 사용할 수 없다.)

이를 일반화하면

0행 j열 (j >= 2)의 값은 1행의 j - 1, j - 2 값이 결정한다.
1행 j열 (j >= 2)의 값은 0행의 j - 1, j - 2 값이 결정한다.

따라서 이를 코드화 하면 다음과 같다.

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]))

참고

https://pacific-ocean.tistory.com/197