[백준] 9465 스티커 (파이썬 python)

 

 

문제 링크

 

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

9465번: 스티커

 

 

문제 설명

 

 

 

 

문제 풀이

 

	0	1	2	3	4
0	50	10	100	20	40
1	30	50	70	10	60

 

 

이 문제는 패턴이 잘 눈에 띄지 않아서 어려웠는데, 결과적으로 굉장히 간단한 패턴을 찾을 수 있다.

예를 들어, dp[0][2]를 선택하고 싶을 경우 앞에서는

dp[1][0] 혹은 dp[1][1]을 선택해야 하는데 둘 중 큰 것을 선택해야만 한다.

dp[1][2]를 선택하고 싶을 경우 앞에서는

dp[0][0] 혹은 dp[0][1] 중 큰 것을 선택해야 할 것이다.

이것을 열의 크기만큼 반복하면 되는 문제이다.

단, 1열의 원소의 최댓값을 구하기 위해서는 0열의 대각선 원소를 선택하여 더해주어야 한다.

반복적으로 시행한 계산을 통해 최댓값을 순차적으로 더해주어 마지막 n-1열의 0행, 1행 값 중 큰 것이 최대가 된다.

 

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]))