스티커[백준 9465] - python

import sys
input = sys.stdin.readline

def BOJ9465() :
  T = int(input())
  for _ in range(T) :
    n = int(input())
    sticker = []
    for _ in range(2) :
      sticker.append(list(map(int, input().split())))
    dp = [[0 for _ in range(n)] for _ in range(2)]
    dp[0][0], dp[1][0] = sticker[0][0], sticker[1][0]
    for i in range(1, n) :
      dp[0][i] = max(dp[1][i-1] + sticker[0][i], dp[0][i-1])
      dp[1][i] = max(dp[0][i-1] + sticker[1][i], dp[1][i-1])
    
    print(max(dp[0][n-1], dp[1][n-1]))

BOJ9465()

 

접근 방법 :

1. 선택을 하는데 있어 이전의 결과값이 영향을 끼치는 것으로 파악하여 dp를 적용해야 겠다 싶었다.

2. 해당 칸에서 선택을 하는 경우와 선택을 하지 않는 경우가 있을것으로 판단하였다.

3. 선택을 할수 있는경우 조건이 있으므로

선택을 하는 경우 이전의 선택할수 있는 조건칸 + 선택한 스티커의 가치 vs 선택을 하지 않으면 이전의 결과값을 그대로 가져와 비교 하였다

 

고민했던 내용들 :

1. 선택한 경우와 선택하지 않는 경우를 떠올리는 것이 쉽게 떠오르지 않았다.

 

 

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

9465번: 스티커