boj 9465 : 스티커

문제 주소: https://www.acmicpc.net/problem/9465

난이도: silver 1

1.문제설명

• 2 by N의 스티커 판이 주어진다.
• 스티커 한개를 뜯으면 그 스티커와 변을 공유하는 스티커는 손상된다.
• 스티커마다 점수가 있는데, 뜯겨진 스티커의 점수 최대값은?

2.문제해결 아이디어.

• 스티커의 왼쪽부터 뜯는다고 생각해보자
• dp테이블을 추가로 만들지 않고, 주어진 스티커 정보 테이블을 사용한다.

3.문제접근법

• 한개의 스티커를 뜯을때 고려할 사항은 바로 왼쪽 스티커를 뜯었는지, 두번째 왼쪽 스티커를 뜯었는지
• 두가지 경우 중 더 큰 경우에 현재 스티커가 가진 점수값을 더해주면서 업데이트
• 아래와 같은 방법으로 업데이트 시켜줌

for i in range(2,N):
            stickers[0][i] += max(stickers[1][i-1], stickers[1][i-2])#두번째 왼쪽 스티커 뜯음, 바로 왼쪽 스티커 뜯음
            stickers[1][i] += max(stickers[0][i - 1], stickers[0][i - 2])

4.특별히 참고할 사항

• 이렇게 정보가 테이블 형태로 주어지면 굳이 dp테이블을 만들 필요가 없다.

5.코드구현

T = int(input())
ans = []
for i in range(T):
    N = int(input())
    stickers = []
    for i in range(2):
        stickers.append(list(map(int, input().split())))
    if len(stickers[0]) == 1:
        ans.append(max(stickers[0][0], stickers[1][0]))
    else:
        stickers[0][1] += stickers[1][0]
        stickers[1][1] += stickers[0][0]
        for i in range(2,N):
            stickers[0][i] += max(stickers[1][i-1], stickers[1][i-2])
            stickers[1][i] += max(stickers[0][i - 1], stickers[0][i - 2])
        ans.append(max(stickers[0][N-1], stickers[1][N-1]))

for j in ans:
    print(j)