[테스트케이스 추가] 백준 9465: 스티커 python, 파이썬

1. 문제

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

9465번: 스티커

 

 

 

2. 풀이

다음 두 가지 경우를 포함시켜 주면 된다.

n 번째 아랫줄의 최댓값은 (n-1 윗줄 or n-2 두 개 중 최댓값) + n번째 아랫줄의 value

 

 

 

3. 구현

import sys
sys.setrecursionlimit(10**8)
sys.stdin=open('input.txt')

T= int(sys.stdin.readline())

def dp(r,n, mm, lis):
  if mm[r][n]!=-1:
    return mm[r][n]
  mm[r][n] = max( int(lis[r][n])+dp((r+1)%2,n-1,mm,lis), max(dp(r,n-2,mm,lis),dp((r+1)%2,n-2,mm,lis))+int(lis[r][n]) )
  return mm[r][n] 

while T:
  T-=1
  n= int(sys.stdin.readline())
  
  lis=[]
  for _ in range(2):
    lis.append(sys.stdin.readline()[:].split())
  mm=[[-1 for _ in range(n+2)] for __ in range(2)]

  mm[0][0]=int(lis[0][0])
  mm[1][0]=int(lis[1][0])
  mm[0][1]=int(lis[0][1])+mm[1][0]
  mm[1][1]=int(lis[1][1])+mm[0][0]

  res = max(dp(0,n-1,mm,lis), dp(1,n-1,mm,lis))
  # print(mm)
  print(res)

 

4. 테스트케이스 추가

 

2
8
178 156 151 197 10 92 148 192
161 175 28 21 71 66 60 63
20
58 189 118 126 59 177 103 139 91 86 114 38 181 58 189 187 5 69 70 4
195 122 19 125 138 195 123 36 170 103 143 38 18 22 7 107 65 58 177 147

답:

965
2284

 

3
5
13 58 28 64 18
90 18 66 57 59
4
19 33 61 2
2 63 35 18
10
64 20 71 88 32 63 61 11 50 7
7 78 67 18 77 32 70 45 66 67

답:

337
161
557