알고리즘/백준[baekjoon]

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

코딩하는이씨 2022. 9. 18. 17:50
728x90
반응형

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

 

9465번: 스티커

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의

www.acmicpc.net

 

정답 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값을 출력해주면된다.

728x90
반응형