[백준] 9465 스티커

📖 문제

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

💻 내 코드

T=int(input())

for _ in range(T):
    n=int(input())
    mlist=[list(map(int, input().split())) for _ in range(2)]

    dp=[[0]*n for _ in range(2)]

    dp[0][0]=mlist[0][0]
    dp[1][0]=mlist[1][0]

    for i in range(1, n):
        if i==1:
            dp[0][i]=dp[1][i-1]+mlist[0][i]
            dp[1][i]=dp[0][i-1]+mlist[1][i]
        else:
            dp[0][i]=mlist[0][i]+max(dp[1][i-1], dp[1][i-2])
            dp[1][i]=mlist[1][i]+max(dp[0][i-1], dp[0][i-2])


    print(max(dp[0][n-1], dp[1][n-1]))

💡풀이

• 합을 저장하기 위해 스티커 배열과 같은 크기의 배열을 만든다
• 열 인덱스가 1일 때는 대각선 왼쪽의 수만 더할 수 있다
• 열 인덱스 2부터는 대각선 왼쪽의 수와 대각선 왼쪽의 수 바로 왼쪽의 수 중 더 큰 수를 더해줄 수 있다