[baekjoon] 백준 9465번 : 스티커 (by python 파이썬)

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

9465번: 스티커

 

정답 code

#스티커
import sys
input = sys.stdin.readline

t = int(input())

for _ in range(t):
    case = []
    n = int(input())
    for i in range(2):
        case.append(list(map(int,input().split())))
    for j in range(1,n):
        if j == 1:
            case[0][j] += case[1][j-1]
            case[1][j] += case[0][j-1]
        else:
            case[0][j] += max(case[1][j-1], case[1][j-2])
            case[1][j] += max(case[0][j-1], case[0][j-2])
    print(max(case[0][n-1],case[1][n-1]))

 

solution

 

이 문제의 최대값을 구해가는 과정에 두가지를 생각해야 한다.

50	10	100	20	40
30	50	70	10	60

문제 예시와 같이 점수가 있다고 가정해보자

이 예시의 최대 값을 구해나가는 과정은 아래와 같다.

50	10 + (30) = 40	100 + MAX(100,30)
30	50 + (50) = 100	70 + MAX(40,50)

index[1][2]값을 보면 원래 저장되있는 값70 에 바로전 대각선에 저장된 값 40이 아닌 그 왼쪽의 50을 더하는게 더 커지는 경우가 있다. 

이런경우를 위해 index[][2]이후로는 바로 직전 대각선 뿐만 아니라 그 왼쪽에 위치한 값중에서 큰값을 더해주어야 최대값을 구할 수 있다.

case[0][j] += max(case[1][j-1], case[1][j-2])
case[1][j] += max(case[0][j-1], case[0][j-2])

 

이렇게 끝까지 더해가며 최대값을 구한뒤 index[0]과 [1]의 끝부분중 max값을 출력해주면된다.