코테 백준 9465 실버1

백준 9465

처음에는 예제를 아이패드로 그려보면서 규칙을 찾았다. [1][0]스티커의 최대값은 [0][1]스티커+[1][0], [1][1]스티커의 최댓값은 [0][0]+[1][1]이다. 이건 확정적이고 그럼 서로 계속 엇갈려 가다가 마지막에 2개 남았을 때 자기와 다른 행의 다음번째 열을 택할지 자기와 다른행의 다음다음번째 열을 택할지 max함수를 사용해서 구하면 되지않을까?했다.

import sys
input=sys.stdin.readline

for i in range(int(input())):
    n=int(input())
    sticker=[list(map(int,input().split())) for _ in range(2)]
    dp=[[0]*n for _ in range(2)]

    dp[0][0]=sticker[0][0]
    dp[1][0]=sticker[1][0]

    if n==1:
        print(max(sticker[0]))
    elif n==2:
        print(max(sticker[0][0]+sticker[1][1],sticker[0][1]+sticker[1]))
    else:
        for i in range(1,n):
            for j in range(2):
                if j==0:
                    dp[j][i]=dp[1][i-1]+sticker[j][i]
                else:
                    dp[j][i]=dp[0][i-1]+sticker[j][i]
                if i==n-3 and j==0:
                    print(dp[j][i]+max(sticker[1][i+1],sticker[1][i+2]))
                    break
                elif i==n-3 and j==1:
                    print(dp[j][i]+max(sticker[0][i+1],sticker[0][i+2]))
                    break

                    

예제는 답이 맞았지만 실행결과 오답이였다. 내가 일반화를 잘못했나보다라고 느껴 다시 풀었는데 스티커를 택하기 전에 선택지가 2개가 나왔다.

1. 2행0번째 스티커를 택한다고 할 때 1행0번째 스티커를 택하고 2행0번째 스티커를 택해 못쓰는 스티커들이 서로 겹치는게 없을 때
2. 2행0번째 스티커를 택한다고 할 때 1행1번째 스티커를 택하고 2행0번째 스티커를 택해 못쓰는 스티커들이 서로 겹치는게 있을 때

이 두가지 중 max를 이용해서 풀어서 정답이 나왔다.

t = int(input())
for i in range(t):
    s = []
    n = int(input())
    for k in range(2):
        s.append(list(map(int, input().split())))
    for j in range(1, n):
        if j == 1:
            s[0][j] += s[1][j - 1]
            s[1][j] += s[0][j - 1]
        else:
            s[0][j] += max(s[1][j - 1], s[1][j - 2])
            s[1][j] += max(s[0][j - 1], s[0][j - 2])
    print(max(s[0][n - 1], s[1][n - 1]))