[백준] 9465번(스티커)

백준 9465번

최종 제출 코드

repeat = int(input().rstrip())

for l in range(repeat):
  n = int(input().rstrip())
  array = [0 for i in range(2)]
  dp = [0,0,0]
  
  for j in range(2):
    array[j] = list(map(int, input().split()))
  
  for k in range(n):
    ele1 = max(dp[0], dp[1], dp[2])
    ele2 = max(dp[0]+array[1][k], dp[2]+array[1][k])
    ele3 = max(dp[0]+array[0][k], dp[1]+array[0][k])
    dp[0] = ele1
    dp[1] = ele2
    dp[2] = ele3
    
  print(max(dp))

◼ 동물원 문제 풀이와 비슷

• 이번 문제에서는 경우의 수가 아닌 array에 담긴 스티커의 값을 더한 값을 비교하여 dp 갱신
• 이번에 (X, X)이면 아무런 스티커도 뜯지 않는다는 뜻 ⇒ 이전 열에서의 최대값을 그대로 갱신. 이처럼 (X, O), (O, X) 케이스도 처리