[백준][Python] 9465번 스티커 - 코팩

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

9465번: 스티커

풀이

최대 누적값을 구하는 문제이기에 dp를 사용하여서 시간 소모를 최소화해야한다.

 

스티커를 찢는 방법은 다음과 같다.

1) 지그재그로 찢는 경우.

2) 한칸 띄고 다른 행의 스티커를 찢는 경우.

A라는 스티커의 위치를 잡아놓고 어떤 스티커를 찢어야 A를 찢을 수 있는지 확인해보면  dp점화식을 만들 수 있다.

 

코드

# 9465번 스티커
t = int(input())
for _ in range(t):
    n = int(input())
    # 누적값을 저장할 리스트이자 주어진 숫자를 저장해둔 리스트.
    dp = [list(map(int, input().split())) for _ in range(2)]
    # 초기값 설정 n이 1보다 큰 경우. 지그재그로 스티커를 찢었을 경우.
    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-2], dp[1][i-1])
        dp[1][i] += max(dp[0][i-2], dp[0][i-1])

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

출력결과