[백준/Python] 9465 스티커

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

9465번: 스티커

 

우선 dp 표를 만들어준다.

시작 기준은 맨 왼쪽 첫째 열, 즉 (1,0), (0,1)로 시작하고, 두 케이스별로 가장 유리한 방식으로 더해나간다.

그후 max 함수를 이용해 최종 두 케이스 중 가장 값이 큰 것을 고르도록 한다.

이때 규칙은 스티커 하나를 고르면 자신의 오른쪽 1칸 대각선 혹은 2칸 대각선 둘 중 하나를 고를 수 있다는 것이다.

 

t = int(input())

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

 # dp 테이블 세팅
 # 왼쪽 첫 째열(시작점)
 if 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]))