BOJ(스티커) 9465

작성일 | In

9465 스티커

  • 스티커 선택시, 선택한 스티커의 상, 하, 좌, 우에 위치한 스티커를 고르지 않으면서 얻을 수 있는 최대 점수를 구하는 것
  • 따라서 어떤 스티커를 시작점으로 할 것인지를 먼저 선택해야 한다.
  • 스티커판은 Nx2의 크기로 세로는 2로 고정되어 있으나, 가로는 N으로 가변적이기 때문에 고정된 2를 활용하도록 한다.
  • 따라서 첫째 줄의 첫째 칸에서 시작하여 얻을 수 있는 최대 점수와 둘째 줄의 첫째 칸에서 시작하여 얻을 수 있는 최대 점수, 이렇게 2가지 경우로 나눠서 접근하겠다.
# 첫째 줄의 첫째칸부터 접근한 것과
# 둘째 줄의 첫쨰칸부터 접근한 것 나눠서 생각

for _ in range(int(input())):
    n = int(input())
    a = [[0]+list(map(int, input().split())) for _ in range(2)]
    d = [[0]*(n+1) for _ in range(2)]
    d[0][1] = a[0][1]
    d[1][1] = a[1][1]
    for i in range(2, n+1):
        d[0][i] = max(d[1][i-1], d[1][i-2]) + a[0][i]
        d[1][i] = max(d[0][i-1], d[0][i-2]) + a[1][i]
    print(max(d[0][n], d[1][n]))

참고자료 codeplus 참고블로그

0%