[백준 - Python] 9465. 스티커

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

9465번: 스티커

 

코드

T = int(input())

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

    if n == 1:
        print(*max(dp))
    
    elif n > 1:
        dp[0][1] += dp[1][0]
        dp[1][1] += dp[0][0]

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

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

 

이 문제의 핵심 포인트는

단순히 지그재그 경로로는 최댓값을 구할 수 없음을 깨닫고

한 열을 건너뛰어서 떼는 것이 최대가 될 수 있음을 고려해서 푸는 것이다!

 

다시 말하자면,

계속 지그재그로 가는 경우와 한 열을 건너 뛰어서 가는 경우를 비교해서

최댓값이 저장되도록 한다

 

dp 테이블을 스티커에 적힌 숫자들로 초기화를 해주고

위에서 언급한 방식대로 갱신한 후에

두 가지 경로 중 더 값이 큰 경로를 선택하여 출력해주면 된다.