백준 9465 스티커

문제 풀이

a0	a1	a2	a3	a4
b0	b1	b2	b3	b4

 스티커가 위와 같이 있다고 할 때, r번 행의 c번 열 스티커를 붙였을 때의 최댓값을 dp[r][c]라 하면, dp의 점화식은 아래와 같이 쓸 수 있다.

 r=0 인 경우 : dp[0][i] = max(dp[0][i-2],dp[1][i-2],dp[1][i-1])+s[0][i]

 r=1 인 경우 : dp[1][i] = max(dp[1][i-2],dp[0][i-2],dp[0][i-1])+s[1][i]

 

 위의 그림에서 a3를 붙였을 경우를 예로 들면, 스티커를 앞에서부터 붙인다면 a1, b1, b2를 붙인 다음에 a3를 붙이는 경우가 가능하다.

 

Python Code

import sys
def solution(s):
  dp = [[s[i][0]] + [0]*(len(s[0])-1) for i in range(2)]
  dp[0][1] = dp[1][0]+s[0][1]
  dp[1][1] = dp[0][0]+s[1][1]
  for i in range(2,len(s[0])):
    dp[0][i] = max(dp[0][i-2],dp[1][i-2],dp[1][i-1])+s[0][i]
    dp[1][i] = max(dp[1][i-2],dp[0][i-2],dp[0][i-1])+s[1][i]
  print(max(dp[0][-1],dp[1][-1]))
 
if __name__=="__main__":
  n = int(input())
  for _ in range(n):
    size = int(input())
    s = []
    for i in range(2):
      s.append(list(map(int,sys.stdin.readline().split())))
    solution(s)

Line 3 ~ 5 : Line 6의 for문으로 dp를 처리하는 과정에서 dp[r][i-2] 연산이 들어가므로 첫 번째, 두 번째 열(c=0,1)을 미리 처리해야 한다.

문제 링크

9465번: 스티커